Section 2.3 - Combinations

Given $n$ distinct items, there are $P(n, k)$ permutations of $0 \leq k \leq n$ items. Each permutation of $k$ items can be re-arranged $k!$ ways. If item order doesn’t matter, there are
$$\frac{P(n, k)}{k!} = \frac{n!}{k!(n-k)!} = C(n, k)$$
orderless permutations, or combinations. Sanity check: $C(n, n) = n!/(n!(n - n)!) = 1/0! = 1$.

Combinations are fun to play with. First, $C(n, k) = C(n, n - k)$.^?And so $C(n, 0) = C(n, n - 0) = 1$. Then
$$\begin{eqnarray} C(n, k + 1) & = & \frac{n!}{(k + 1)!(n - k - 1)!} \\ & = & \frac{n!(n - k)}{(k + 1)k!(n - k)(n - k - 1)!} \\ & = & \frac{n - k}{k + 1}C(n, k) \end{eqnarray}$$
$C(n, k + 1)$ is largest when $(n - k)/(k + 1)$ is closest to 1, which occurs when $k$ is closest to $(n - 1)/2$. Similarly
$$\begin{eqnarray} C(n + 1, k) & = & \frac{(n + 1)!}{k!(n + 1 - k)!} \\ & = & \frac{(n + 1)n!}{k!(n + 1 - k)(n - k)!} \\ & = & \frac{n + 1}{n + 1 - k}C(n, k) \end{eqnarray}$$