The combination statistic $C(n, k)$ counts the total number of subsets of size $k$
that can be constructed from a set of $n$ given elements.
Another way of writing $C(n, k)$ is as $\binom{n}{k}$, read "$n$ choose $k$."
Because a set is always a subset of itself, and the empty set is a subset of every set,
we will have that $\binom{n}{0} = \binom{n}{n} = 1$ for all $n$.
Combinations are also known as binomial coefficients, which derives from the binomial theorem.
This result states that if we expand the expression $(x+y)^n$ for a positive integer $n$, we will
obtain $(x+y)^n = \sum\limits_{k=0}^{n}\binom{n}{k}x^k y^{n-k}$. For example,
$(x+y)^4 = x^4 + 4x^3 y + 6x^2 y^2 + 4x y^3 + y^4$.
The binomial coefficients can be combined into a structure called Pascal's triangle. The
$n$-th row of this triangle contains $\binom{n}{0}, \binom{n}{1}, \ldots, \binom{n}{n}$.
The first five rows of this triangle are depicted below.
The reason why combinations are entered into Pascal's triangle in the above way is so that
a pattern will emerge: a given combination is equal to the sum of the two combinations above it.
In mathematical terms, this states that $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$,
and it can be explained by noting that if we would like to form a subset $T$ containing $k$ elements from
a set $S$ containing $n$ elements ($\binom{n}{k}$ possibilities), then for any element $x$ in $S$,
$x$ can either be in $T$ (leaving $\binom{n-1}{k-1}$ possibilities for selecting the remaining elements of $T$) or
not in $T$ (leaving $\binom{n-1}{k}$ possibilities for choosing the elements of $T$).
A number of further identities exist dictating the relationships between combinations
and creating patterns in Pascal's triangle, which we encourage you to explore.
