Binomial Coefficients¶

There are several ways to think about the binomial coefficients. On this page I explain some of the most common ways. On this page, $n$ and $k$ are integers such that $0 \le k \le n$.

Binomial formula¶

Consider the formula $$ (a+b)^2 = a^2+2ab+b^2. $$ There is a similar formula for $(a+b)^3$. To get it from this one, we can calculate $$ \begin{align} (a+b)^3 &= (a+b)^2(a+b) \\ &= (a^2+2ab+b^2)(a+b) \\ &= (a^2+2ab+b^2)a + (a^2+2ab+b^2)b \\ &= a^3+2a^2b+ab^2+a^2b+2ab^2+b^3 \\ &= a^3+3a^2b+3ab^2+b^3. \end{align} $$ By multiplying this with $(a+b)$ again, we can get a formula for $(a+b)^4$: $$ \begin{align} (a+b)^4 &= (a+b)^3(a+b) \\ &= (a^3+3a^2b+3ab^2+b^3)(a+b) \\ &= a^4+3a^3b+3a^2b^2+ab^3+a^3b+3a^2b^2+3ab^3+b^4 \\ &= a^4+4a^3b+6a^2b^2+4ab^3+b^4 \end{align} $$

In general, we can make the formula for $(a+b)^n$ from the previous $(a+b)^{n-1}$ formula. Notice the formulas produced this way have these properties:

• The formulas are sums of terms with an integer, some number of $a$'s, and some number of $b$'s multiplied. For example, in $3a^2b$, the integer is $3$ and there is two $a$'s and one $b$. In $a^2$, we have zero $b$'s, and the integer is $1$.
• The total number of $a$'s and $b$'s in each term is $n$. For example, $3a^2b$ contains two $a$'s and one $b$, $2+1=3=n$ in total. So, if $a$ occurs $k$ times in the $(a+b)^n$ formula, as in $a^k$, then $b$ occurs $n-k$ times and we have $a^kb^{n-k}$ multiplied by some integer, such as $a^2b$ for $n=3$ and $k=2$. This happens for all $n$ because if it happens for the previous $(a+b)^{n-1}$ formula, then we end up with one more $a$ or $b$ everywhere in the $(a+b)^n$ formula.
• If we know the integers in front of $a^k b^{n-k}$ for each $k$ in the range $0 \le k \le n$, then we know the entire $(a+b)^n$ formula.

The integer in front of $a^kb^{n-k}$ when expanding $(a+b)^n$ is called the binomial coefficient, and it's denoted with $\binom{n}{k}$. So for example, because there is $3$ in front of $a^2b$ in the $(a+b)^3$ formula, we have $$ \binom{3}{2}=3, $$ and for all $n$, the numbers in front of $a^n$ and $b^n$ are $$ \binom{n}{n} = 1, \quad \binom{n}{0} = 1. $$

This also works for $n=1$ and $n=0$ with all binomial coefficients being $1$, because $$ \begin{align} (a+b)^1 &= 1a^1b^0 + 1a^0b^1, \\ (a+b)^0 &= 1a^0b^0. \end{align} $$ Next we find a way to calculate binomial coefficients.

Pascal's triangle¶

Let's arrange all binomial coefficients we know into a big triangle-shaped drawing like this: $$ \begin{matrix} &&&&\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{2}{2}&&\binom{3}{3}& \\ \binom{4}{0}&&\binom{4}{1}&&\binom{4}{2}&&\binom{4}{3}&&\binom{4}{4} \\ &&&&\vdots&&&& \end{matrix} $$ The three dots in the bottom of the drawing mean that it goes on infinitely; by making more $(a+b)^n$ formulas, we can extend the triangle downwards as much as we want. By plugging in the numbers from the formulas we know, the triangle becomes $$ \begin{matrix} &&&&1&&&&\\ &&&1&&1&&&\\ &&1&&2&&1&&\\ &1&&3&&3&&1&\\ 1&&4&&6&&4&&1 \\ &&&&\vdots&&&& \end{matrix} $$ This is known as Pascal's triangle.

If you look carefully, you might notice that whenever there's two numbers next to each other, their sum is below them. For example, below I colored $\green3+\blue3 = \red6$: $$ \begin{matrix} &&&&1&&&&\\ &&&1&&1&&&\\ &&1&&2&&1&&\\ &1&&\green3&&\blue3&&1&\\ 1&&4&&\red6&&4&&1 \\ &&&&\vdots&&&& \end{matrix} $$ So, we noticed that $$ \green{\binom{3}{1}}+\blue{\binom{3}{2}}=\red{\binom{4}{2}}, $$ and more generally, it seems like $$ \green{\binom{n}{k}}+\blue{\binom{n}{k+1}}=\red{\binom{n+1}{k+1}}. $$ To see why this happens, consider $$ (a+b)^n = \binom{n}{n}a^n + \dots + \blue{\binom{n}{2}}a^2b^{n-2} + \green{\binom{n}{1}}ab^{n-1} + \binom{n}{0}b^n. $$ Let's multiply this with $a$ and $b$: $$ \begin{alignat}{9} (a+b)^na &= \binom{n}{n}a^{n+1} &+ \dots &+ \blue{\binom{n}{2}}a^3b^{n-1} &+ \green{\binom{n}{1}}a^2b^{n-1} &+ \binom{n}{0}ab^n \\ (a+b)^nb &=& \binom{n}{n}a^nb &+ \dots &+ \blue{\binom{n}{2}}a^2b^{n-1} &+ \green{\binom{n}{1}}ab^n &+ \binom{n}{0}b^{n+1}& \\ \end{alignat} $$ By adding these equations, we get $$ (a+b)^{n+1} = \dots + \left( \green{\binom{n}{1}}+\blue{\binom{n}{2}} \right)a^2b^{n-1} + \dots, $$ where $\dots$ does not contain any $a^2b^{n-1}$. So, the number in front of $a^2b^{n-1}$ is $$ \green{\binom{n}{1}}+\blue{\binom{n}{2}}, $$ and because on the other hand, there should be $\red{\binom{n+1}{2}}$ in front of $a^2b^{(n+1)-2}$, we get $$ \green{\binom{n}{1}}+\blue{\binom{n}{2}} = \red{\binom{n+1}{2}}, $$ which is the equation we wanted for $k=1$. It works the same way for any other $k$, and we get $$ \green{\binom{n}{k}}+\blue{\binom{n}{k+1}} = \red{\binom{n+1}{k+1}}. $$

Subsets¶

Consider a set of two elements, $\{A,B\}$. It has these subsets:

• The empty set
• $\{A\}$
• $\{B\}$
• $\{A,B\}$

In particular, note that any set is a subset of itself. Also, the same element can't occur several times in a set, and order does not matter; $\{A,B\}$ and $\{B,A\}$ are the same set.

A set of 3 elements, $\{A,B,C\}$, has these subsets:

• The empty set
• $\{A\}$
• $\{B\}$
• $\{C\}$
• $\{A,B\}$
• $\{A,C\}$
• $\{B,C\}$
• $\{A,B,C\}$

Note that a set of 2 elements has 1 subset of 0 elements, 2 subsets of 1 element and 1 subset of 2 elements, $1\,\,2\,\,1$. The sizes of subsets of a set of 3 elements are $1\,\,3\,\,3\,\,1$. These are rows $2$ and $3$ of Pascal's triangle when we think of the first row as row $0$ and first column of each row as column $0$. In other words, the number of subsets of $k$ elements in a set of $n$ elements seems to be $$ \binom{n}{k}. $$ Next we explain why this happens.

Let $C(n,k)$ denote the number of subsets of $k$ elements in a set of size $n$. Consider the triangle $$ \begin{matrix} &&&C(0,0)&&& \\ &&C(1,0)&&C(1,1)&& \\ &C(2,0)&&C(2,1)&&C(2,2)& \\ C(3,0)&&C(3,1)&&C(2,2)&&C(3,3) \\ &&&\vdots&&& \end{matrix} $$ Next we explain why this triangle is same as Pascal's triangle. We need to ensure two things:

• This triangle has $1$ at the edges: $C(n,0)=1$ and $C(n,n)=1$
• Each number in this triangle is the sum of the two numbers above: $C(n,k)+C(n,k+1)=C(n+1,k+1)$

The first property is clear; a set of $n$ elements has only one subset of zero elements (empty set) and only one subset of $n$ elements (the set itself). For the second property, imagine going into shop that sells $n+1$ different products, milk and $n$ other things, with a shopping bag that fits exactly $k+1$ products. We calculate the number of ways how you can fill the shopping bag without choosing the same product twice:

• If you choose milk, then you need to fill the shopping bag with $k$ more products, chosen out of the $n$ remaining products (milk excluded). This can be done in $C(n,k)$ different ways.
• If you don't choose milk, then you need to choose $k+1$ other products to fill the shopping bag, out of the $n$ non-milk products available. This can be done in $C(n,k+1)$ different ways.

In total, $$ \begin{align} C(n+1,k+1) &= \text{number of ways to fill shopping bag} \\ &= \underbrace{C(n,k)}_{\text{milk}} + \underbrace{C(n,k+1)}_{\text{no milk}}. \end{align} $$ This shows that these $C(n,k)$ numbers are binomial coefficients, because they form Pascal's triangle.

For this reason, binomial coefficients are often spelled "$n$ choose $k$"; they represent the number of different ways to choose $k$ items from $n$ items when the order of the items is ignored and you can't choose the same item twice.

Formula¶

We still don't have a formula for calculating binomial coefficients, although looking them up from Pascal's triangle is easy enough for small-ish values of $n$.

Consider a shop with $n$ products and a shopping bag that fits exactly $k$ products. The number of ways to fill the shopping bag without choosing the same product twice is then $\binom{n}{k}$. To find a formula for this, we need a different way to calculate the number of ways to fill the shopping bag.

• If $k=0$, there's only one thing you can do: leave the shop with an empty shopping bag. $$ \binom{n}{0} = 1 $$
• If $k=1$, there are $n$ ways to fill the shopping bag, because you choose one of the $n$ available products. $$ \binom{n}{1} = n $$
• If $k=2$, you have $n$ choices for the first product to buy, but only $n-1$ choices for the second product because you can't choose the same product twice. This gives a total of $n(n-1)$ choices. But now we calculated $\{ \text{milk}, \text{bread} \}$ and $\{ \text{bread}, \text{milk} \}$ as two different subsets of the set of products in the store, because you can choose milk first and then bread, or vice versa. For that reason, $n(n-1)$ is not the number we are looking for; it's two times too big, since each subset was counted twice. To correct this, we must divide by 2, and we get $$ \binom{n}{2} = \frac{n(n-1)}{2}. $$
• If $k=3$, you have $n(n-1)$ choices for the first two products, including different orders, and $n-2$ choices for the third product, giving a total of $n(n-1)(n-2)$ choices. Now every subset got counted 6 times, because there are 6 ways to sort 3 products: $$ \begin{align} \{ \text{milk},\text{bread},\text{cheese} \} \\ \{ \text{milk},\text{cheese},\text{bread} \} \\ \{ \text{cheese},\text{milk},\text{bread} \} \\ \{ \text{cheese},\text{bread},\text{milk} \} \\ \{ \text{bread},\text{cheese},\text{milk} \} \\ \{ \text{bread},\text{milk},\text{cheese} \} \end{align} $$ To correct this, we must divide by 6 and we get $$ \binom{n}{3} = \frac{n(n-1)(n-2)}{6}. $$

In general, $$ \binom{n}{k} = \frac{\overbrace{n(n-1)(n-2)\dots}^{\text{$k$ numbers multiplied}}}{\text{number of ways to sort a set of $k$ items}}, $$ where on top, we have the first $k$ numbers of $n,~ n-1,~ n-2,~ n-3,~ \dots$ multiplied. Next find the ways that a set of $k$ items can be sorted. If $k=n$, then on top we multiply all integers between $n$ and $1$ (inclusive). We call that $$ n! = n(n-1)(n-2)\dots 1, $$ so for example, $5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1$. Now we get $$ \binom{n}{n} = \frac{n!}{\text{number of ways to sort a set of $n$ items}}, $$ and because $\binom{n}{n} = 1$, we get $$ \text{number of ways to sort a set of $n$ items} = n!. $$ By using this with $k$ instead of $n$, we get the following result.

For example, $$ \binom{8}{3} = \frac{8 \cdot 7 \cdot 6}{3 \cdot 2 \cdot 1} = 56. $$