Combinations without replacement

The only difference between this case and the case of permutations without replacement is that the selection order of the k selected objects is not distinguished here. This implies that a different arrangement of the same objects is not counted for this case and so this case involves simply selecting a subset of size k from the population. Therefore, we can view the number of permutations without replacement as a two-stage process: first select a subset (combinations without replacement) and then generate every possible rearrangement of each of these subsets. Note that the number of ways to generate every possible rearrangement of k objects is equivalent to counting the number of permutations without replacement of k objects selected from a population of size k, and so is equal to k!. Denote by C(n,k) the number of combinations without replacement. Then we have,

$$\frac{n!}{(n-k)!} = C(n,k)k!.$$

Hence,

$$C(n,k) = \frac{n!}{k!(n-k)!}.$$

This quantity is usually denoted by

$${n\choose k}$$