Binomial Coefficients

In Combinations, we introduced binomial coefficients \( \binom{n}{k} \) as the number of ways to choose \( k \) objects from a set of size \( n \). Binomial coefficients also arise naturally when considering powers of binomial expressions, as shown in the following theorem.

Binomial Theorem: If $a, b$ are variables and $n$ is a positive integer, then

$\displaystyle (a+b)^n = \sum_{i = 0}^{n}\binom{n}{i}a^{i}b^{n-i} .$

The two different ideas mentioned above are actually very closely related to each other. When we expand $(a + b)^{n}$, each term in the expansion comes from choosing either $a$ or $b$ from each of the $n$ binomials in the product. This is why the terms in our expression are of the form $a^{i}b^{n-i}$. To get the term $a^{i}b^{n-i}$, we have to multiply $i$ copies of $a$ and $n-i$ copies of $b$. If we choose $i$ of the $n$ binomials from which to use the term $a$, then we are left with $n-i$ of the binomials from which to use the term $b$. The total number of ways to choose $i$ of the $n$ binomials is $\binom{n}{i}$, which is why this is the coefficient of the term $a^{i}b^{n-i}$.

The binomial coefficients can be arranged into a chart called Pascal’s Triangle that uses the relation $\binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1}$. The $i$th row of Pascal’s triangle has the binomial coefficients $\binom{i}{0}, \binom{i}{1}, \ldots, \binom{i}{i}$. The first row is considered row 0 and contains the coefficient $\binom{0}{0}$.

$\begin{array}{ccccccccccccc} & & & & & &\binom{0}{0} & & & & & & \\ & & & & &\binom{1}{0} & &\binom{1}{1} & & & & & \\ & & & &\binom{2}{0} & &\binom{2}{1} & &\binom{2}{2} & & & & \\ & & &\binom{3}{0} & &\binom{3}{1} & &\binom{3}{2} & &\binom{3}{3} & & & \\ & &\binom{4}{0} & &\binom{4}{1} & &\binom{4}{2} & &\binom{4}{3} & &\binom{4}{4} & & \\ &\binom{5}{0} & &\binom{5}{1} & &\binom{5}{2} & &\binom{5}{3} & &\binom{5}{4} & &\binom{5}{5} & \\ \binom{6}{0} & &\binom{6}{1} & &\binom{6}{2} & &\binom{6}{3} & &\binom{6}{4} & &\binom{6}{5} & &\binom{6}{6} \\ \end{array}$

By plugging in the values of the binomial coefficients, we obtain Pascal's Triangle:

$\begin{array}{ccccccccccccc} & & & & & & 1 & & & & & & \\ & & & & & 1 & & 1 & & & & & \\ & & & & 1 & & 2 & & 1 & & & & \\ & & & 1 & & 3 & & 3 & & 1 & & & \\ & & 1 & & 4 & & 6 & & 4 & & 1 & & \\ & 1 & & 5 & & 10 & & 10 & & 5 & & 1 & \\ 1 & & 6 & & 15 & & 20 & & 15 & & 6 & & 1 \\ \end{array}$

When working with binomial coefficients, we can generally approach problems in two different ways, either algebraically (by manipulating the expressions), or combinatorially (by interpreting the expressions).

Worked Examples

1. Show algebraically that $\binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1}$.

Solution: We expand the expression on the left hand side in terms of factorials:

$\begin{aligned} \binom{n}{k} + \binom{n}{k+1} = & \frac{n!}{k!(n-k)!} + \frac{n!}{(k+1)!(n-k-1)!}\\ = & \frac{n!(k+1)}{(k+1)!(n-k)!} + \frac{n!(n-k)}{(k+1)!(n-k)!}\\ = & \frac{n!(n+1)}{(k+1)!(n-k)!}\\ = & \frac{(n+1)!}{(k+1)!(n-k)!}\\ = & \binom{n+1}{k+1}\\ \end{aligned}$

2. Show combinatorially that $\binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1}$.

Solution: The right hand side counts the number of ways to choose $k+1$ people from $n+1$ people. If we consider one of the $n+1$ people, then either they are chosen in the set of $k+1$ people or they are not. The number of ways to choose $k+1$ people which includes this person is $\binom{n}{k}$ (we need to choose $k$ of the $n$ other people). The number of ways to choose $k+1$ people which do not include this person is $\binom{n}{k+1}$ (we need to choose $k+1$ of the $n$ other people).

3. Show that $\binom{n}{0} + \binom{n}{1} + \cdots + \binom{n}{n} = 2^{n}$.

Algebraic solution: From the Binomial Theorem, we have

$(a + b)^{n} = \sum_{i = 0}^{n}\binom{n}{i}a^{i}b^{n-i} .$

If we let $a = b = 1$, this expression becomes

$2^n = \sum_{i=0}^{n}\binom{n}{i} = \binom{n}{0} + \binom{n}{1} + \cdots + \binom{n}{n} .$

Combinatorics solution: We use the technique of Double Counting. Consider the number of ways to choose a team out of $n$ players. From Combinations, there are ${ n \choose i}$ ways to choose a team of exactly $i$ players; therefore, the left hand side represents the number of ways to choose a team according to the number of players. On the other hand, we can choose a team by deciding if a specified player is in the team or not. By the Rule of Product, there are $2^n$ ways to do this which is the right hand side. Hence, the two sides are equal.