next up previous
Next: Examples Up: Probability Previous: Permutations with replacement

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,

\begin{displaymath}
\frac{n!}{(n-k)!} = C(n,k)k!.
\end{displaymath}

Hence,

\begin{displaymath}
C(n,k) = \frac{n!}{k!(n-k)!}.
\end{displaymath}

This quantity is usually denoted by

\begin{displaymath}
{n\choose k}
\end{displaymath}



Larry Ammann
2013-12-17