10 Combinations

10.0.1 Lemma

A set of \(n\) elements may be partitioned into \(m\) distinct groups containing \(k_1 , k_2 , \ldots , k_m\) objects, respectively, where each object appears in exactly one group and \(\sum\limits_{i=1}^{m}k_i=n\), in \(\displaystyle N={n\choose k_1k_2\ldots k_m}=\frac{n!}{k_1!k_2!\ldots k_m!}\) ways.\

Proof:

\(N\) is the number of ways all \(n\) of the elements of the set can be arranged in \(m\) groups where the order within each group is not important (i.e. rearrangements of elements in a group do not qualify as distinct groups).

The number of distinct arrangements of the \(n\) elements in which the order of selection is important, \(P_k^n\), is equal to \(N\) multiplied by the number of ways each individual group of \(k_i\) can be selected in which the order is important, i.e.

\[\begin{aligned} P_n^n &= N \cdot P_{k_1}^{k_1} P_{k_2}^{k_2} \cdots P_{k_m}^{k_m} \\ \Rightarrow n! &= N \cdot k_1! k_2! \cdots k_m! \\ \Rightarrow N &= \frac{n!}{k_1! k_2! \cdots k_m!} \end{aligned}\]

10.0.2 Combinations Theorem

Given a set of \(n\) elements, the number of possible ways to select a subset of size \(k\), without regard to the order of their selection, is \(\frac{n!}{k!(n-k)!}\).\

Proof:

This theorem is a special case of the Lemma with \(n=n\), \(m=2\), \(k_1=k\) and \(k_2=n-k\). thus,

\[\displaystyle N=\frac{n!}{k!(n-k)!}\]

The formula \(\displaystyle \frac{n!}{k!(n-k)!}\) is denoted in a number of ways, depending on the author. Denotations may be \(C_k^n\), \(_nC_k\), \(C_{n,k}\), \(C(n,k)\), and \({n\choose k}\).
Throughout this book, the form \({n\choose k}\) is used and may be read “\(n\) choose \(k\) objects.”

10.0.3 Theorem

For any integer \(a\) such that \(0\leq a\leq k\),

\[ {n\choose k} = \frac{n(n-1)(n-2)\cdots(n-a+1)}{k(k-1)(k-2)\cdots(k-a+1)}{n-a\choose k-a} \]

Proof:

\[\begin{aligned} {n\choose k} &= \frac{n!}{k!(n-k)!} \\ &= \frac{n(n-1)!}{k(k-1)!(n-k)!} \\ &= \frac{n(n-1)(n-2)!}{k(k-1)(k-2)!(n-k)!} \\ &= \frac{n(n-1)(n-2)\cdots(n-a+1)(n-a)!}{k(k-1)(k-2)\cdots(k-a+1)(k-a)!(n-k)!} \\ &= \frac{n(n-1)(n-2)\cdots(n-a+1)}{k(k-1)(k-2)\cdots(k-a+1)} \cdot \frac{(n-a)!}{(k-a)!(n-k)!} \\ &= \frac{n(n-1)(n-2)\cdots(n-a+1)}{k(k-1)(k-2)\cdots(k-a+1)} \cdot \frac{(n-a)!}{(k-a)!(n-a+a-k)!} \\ &= \frac{n(n-1)(n-2)\cdots(n-a+1)}{k(k-1)(k-2)\cdots(k-a+1)} \cdot \frac{(n-a)!}{(k-a)![(n-a)+(a-k)]!} \\ &= \frac{n(n-1)(n-2)\cdots(n-a+1)}{k(k-1)(k-2)\cdots(k-a+1)} \cdot \frac{(n-a)!}{(k-a)![(n-a)-(k-a)]!} \\ &= \frac{n(n-1)(n-2)\cdots(n-a+1)}{k(k-1)(k-2)\cdots(k-a+1)} \cdot {n-a\choose k-a} \end{aligned}\]