# 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}