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.