Binomial Coefficients

There are several ways to think about binomial coefficients. On this page I explain the most common ways.

Definition with subsets

Let's define binomial coefficients like this. Later on this page, I will explain why they are called "binomial coefficients".

Let $n$ and $k$ be integers such that $0 \le k \le n$. The binomial coefficient $\binom{n}{k}$, spelled "$n$ choose $k$", is the number of subsets of size $k$ that a set of size $n$ has.

Here "subset" means any set whose elements are contained in the original set. For example, here are all subsets of the set $\{1,2,3\}$:

Sets cannot contain duplicates and the order doesn't matter, so $\{2,1\}$ would be the same set as $\{1,2\}$, and $\{3,3\}$ would be the same set as $\{3\}$. Also note that any set is a subset of itself, and the empty set is a subset of any set.

Based on the above list, we can calculate some binomial coefficients:

Formula

Listing all subsets can be quite painful. For example, to calculate $\binom{7}{3}$, we could take a set of seven elements, say $\{A,B,C,D,E,F,G\}$, and find all subsets of three elements:

I gave up after finding 17 different subsets, which shows that $\binom{7}{3} > 17$. This also shows that we need a better way to calculate binomial coefficients.

Consider picking the 3 elements of the subset one by one:

There are 7 ways to pick the first element, $7 \cdot 6 = 42$ ways to pick the first two elements, and $7 \cdot 6 \cdot 5 = 210$ ways to pick all three elements. Therefore it looks like there are 210 subsets of 3 elements.

Unfortunately this doesn't quite work. The 210 choices above count e.g. both $\{C,E,F\}$ and $\{E,C,F\}$: if you choose $C$ first, you can still choose $E$ and $F$, and if you choose $E$ first, you can still choose $C$ and $F$.

Actually, all subsets were counted 6 times. For example, here are all the 6 ways how the set $\{A,B,C\}$ was counted:

This means that $7 \cdot 6 \cdot 5$ is 6 times too big, and the correct value is $$ \binom{7}{3} = \frac{7 \cdot 6 \cdot 5}{6} = 35. $$ 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$ elements}}, $$ where on top, we have the first $k$ numbers of $n,~ n-1,~ n-2,~ n-3,~ \dots$ multiplied.

Next we count the number of ways how a set of $k$ elements can be sorted. We know that this should produce 6 for $k=3$, because above we listed all ways to sort a set of 3 elements. We can sort a set of $k$ items like this:

For example, here's how this goes for $k=3$ and the set $\{A,B,C\}$:

This produced the order $BCA$, and with other choices, we can get the elements in any order we want. There are $3 \cdot 2 \cdot 1 = 6$ ways to do the above choices, and hence 6 ways to sort a set of 3 elements. In general, there are $k!$ ways to sort a set of $k$ elements, where $k!$ is the factorial of $k$, defined by $$ k! = k \cdot (k-1) \cdot (k-2) \cdot \dots \cdot 3 \cdot 2 \cdot 1. $$

Binomial coefficients can be calculated as $$ \binom{n}{k} = \frac{~~ \overbrace{n(n-1)(n-2)\dots}^{\text{$k$ numbers multiplied}} ~~}{k!}, $$ where $k!= k \cdot (k-1) \cdot \dots \cdot 3\cdot2\cdot1$ is the number of ways to sort a list of $k$ elements.

For example, $$ \binom{7}{3} = \frac{7 \cdot 6 \cdot 5}{3 \cdot 2 \cdot 1} = 35, $$ and $$ \binom{9}{4} = \frac{9 \cdot 8 \cdot 7 \cdot 6}{4 \cdot 3 \cdot 2 \cdot 1} = 126. $$

This result is often written as $$ \binom{n}{k} = \frac{n!}{k!(n-k)!}. $$ Here dividing by $(n-k)!$ deletes the last $n-k$ numbers that were multiplied into $n!$ on top, leaving only the first $k$ numbers. For example, with $n=9$ and $k=4$, it deletes the last 5 numbers and leaves the first 4, like this: $$ \frac{9!}{4!(9-4)!} = \frac{9!}{4! \cdot 5!} = \frac{9 \cdot 8 \cdot 7 \cdot 6 \cdot \cancel{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}}{(4 \cdot 3 \cdot 2 \cdot 1) \cdot \cancel{(5 \cdot 4 \cdot 3 \cdot 2 \cdot 1)}} = \frac{9 \cdot 8 \cdot 7 \cdot 6}{4 \cdot 3 \cdot 2 \cdot 1} $$

Pascal's triangle

Let's draw a triangle shape with ones, like this: $$ \begin{matrix} &&&1&&&\\ &&1&&1&&\\ &1&& &&1&\\ 1&& && &&1\\ \end{matrix} $$ Then, whenever two numbers are next to each other, we write their sum below them (for example, $\blue{1} + \blue{1} = \red{2}$): $$ \begin{matrix} &&&1&&&\\ &&\blue{1}&&\blue{1}&&\\ &1&&\red{2}&&1&\\ 1&& && &&1\\ \end{matrix} $$
$$ \begin{matrix} &&&1&&&\\ &&1&&1&&\\ &\blue{1}&&\blue{2}&&1&\\ 1&&\red{3}&& &&1\\ \end{matrix} $$
$$ \begin{matrix} &&&1&&&\\ &&1&&1&&\\ &1&&\blue{2}&&\blue{1}&\\ 1&&3&&\red{3}&&1\\ \end{matrix} $$ This is called Pascal's triangle.

The numbers in Pascal's triangle look familiar. For example, the row $1,3,3,1$ is actually $\binom{3}{0},\binom{3}{1},\binom{3}{2},\binom{3}{3}$ (see the beginning of this page). Let's draw the triangle a bit more:

$$\begin{matrix}&&&&&&&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& \\1&&7&&21&&35&&35&&21&&7&&1 \\\end{matrix}$$

35 in the bottom row also looks familiar. It is $\binom{7}{3}$. In general, it looks like each row in Pascal's triangle contains the binomial coefficients $\binom{n}{k}$ with fixed $n$ and varying $k$, 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{3}{2}&&\binom{3}{3}&\\ &&&&\vdots&&&& \end{matrix} $$ Consider the triangle of binomial coefficients shown above. For this triangle to be same as Pascal's triangle, it needs to satisfy the two rules we used to build Pascal's triangle:

The ones on the edges make sense, because $\binom{n}{0} = 1$ and $\binom{n}{n} = 1$ for any $n$. The sum rule is more interesting. For example, consider $\red{\binom{5}{3}}$. The numbers above it are $\blue{\binom{4}{2}}$ and $\green{\binom{4}{3}}$. $$ \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{3}{2}&&\binom{3}{3}&&\\ &\binom{4}{0}&&\binom{4}{1}&&\blue{\binom{4}{2}}&&\green{\binom{4}{3}}&&\binom{4}{4}&\\ \binom{5}{0}&&\binom{5}{1}&&\binom{5}{2}&&\red{\binom{5}{3}}&&\binom{5}{4}&&\binom{5}{5}\\ &&&&&\vdots&&&&& \end{matrix} $$ The binomial coefficient $\red{\binom{5}{3}}$ means that we go to a shop that sells 5 different products, e.g. $\{\text{apples},\text{bananas},\text{cheese},\text{donuts},\text{eggs}\}$, and we count the number of ways to put 3 different products to a shopping bag.

So the total number of ways to fill the shopping bag is $\blue{\binom{4}{2}} + \green{\binom{4}{3}}$. But we also know that it's $\red{\binom{5}{3}}$, so $$ \blue{\binom{4}{2}} + \green{\binom{4}{3}} = \red{\binom{5}{3}}. $$

The same reasoning works with any location in the triangle. If you buy $k$ products from a shop that sells $n$ products ($\red{\binom{n}{k}}$), you can either buy apples and $k-1$ other products ($\blue{\binom{n-1}{k-1}}$), or buy $k$ other products ($\green{\binom{n-1}{k}}$), so $$ \red{\binom{n}{k}} = \blue{\binom{n-1}{k-1}} + \green{\binom{n-1}{k}}. $$

Binomial coefficients can be looked up from Pascal's triangle, where we place ones on the edges and the sum of any two adjacent numbers below them. If the top of the triangle is row zero column zero, then $\binom{n}{k}$ is the number in row $n$ column $k$.

$$ \begin{matrix} &&&&1&&&&\\ &&&1&&1&&&\\ &&1&&2&&1&&\\ &1&&3&&3&&1&\\ 1&&4&&6&&4&&1\\ &&&&\vdots&&&& \end{matrix} $$
$$ \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{3}{2}&&\binom{3}{3}&\\ \binom{4}{0}&&\binom{4}{1}&&\binom{4}{2}&&\binom{4}{3}&&\binom{4}{4}\\ &&&&\vdots&&&& \end{matrix} $$

Binomial Formula

I haven't explained yet why binomial coefficients are called binomial coefficients.

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 multiply it by $a+b$: $$ \begin{align} (a+b)^3 &= (a+b)(a+b)^2 \\ &= (a+b)(a^2+2ab+b^2) \\ &= a(a^2+2ab+b^2) + b(a^2+2ab+b^2) \\ &= (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)(a+b)^3 \\ &= (a+b)(a^3+3a^2b+3ab^2+b^3) \\ &= (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} $$ And again: $$ \begin{align} (a+b)^5 &= (a+b)(a^4+4a^3b+6a^2b^2+4ab^3+b^4) \\ &= a^5+5a^4b+10a^3b^2+10a^2b^3+5ab^4+b^5 \end{align} $$

It seems like the integers (coefficients) in front of $a$'s and $b$'s are rows in Pascal's triangle (e.g. $1~4~6~4~1$ for $(a+b)^4$). This is why binomial coefficients are called binomial coefficients: when raising a binomial $a+b$ to a power, they are the coefficients you need to put in front of $a$'s and $b$'s.

Next I explain why the numbers in $(a+b)^n$ formulas form Pascal's triangle. First, let's observe some things that happen when a $(a+b)^n$ formula is created from the previous $(a+b)^{n-1}$ formula:

Let's build a new triangle from the coefficients of $(a+b)^n$ formulas: $$ \begin{matrix} (a+b)^0 = 1 & \to & &&&&&1&&&&&\\ (a+b)^1 = a+b & \to & &&&&1&&1&&&&\\ (a+b)^2 = a^2+2ab+b^2 & \to & &&&1&&2&&1&&&\\ (a+b)^3 = a^3+3a^2b+3ab^2+b^3 & \to & &&1&&3&&3&&1&&\\ (a+b)^4 = a^4+\blue{4a^3b}+\green{6a^2b^2}+4ab^3+b^4 & \to & &1&&\blue{4}&&\green{6}&&4&&1&\\ (a+b)^5 = a^5+5a^4b+\red{10a^3b^2}+10a^2b^3+5ab^4+b^5 & \to & 1&&5&&\red{10}&&10&&5&&1\\ &\vdots& &&&&&&&&&& \end{matrix} $$ For this triangle to be same as Pascal's triangle, it needs to satisfy the two rules we used to build Pascal's triangle:

We get ones on the edges, because the numbers in front of $a^n$ and $b^n$ are always 1.

To see why adjacent numbers are added, think about how we can get $\red{a^3b^2}$ in the $(a+b)^5$ formula when multiplying the previous formula with $a$ and $b$. There are only two ways how this can happen, and any other combination gives the wrong number of $a$'s or $b$'s:

These two ways bring in two adjacent numbers from the previous row, like this: $$ \begin{align} (a+b)(a+b)^4 &= \quad a(a^4+4a^3b+\green{6a^2b^2}+4ab^3+b^4)\\ &\quad {}+ b(a^4+\blue{4a^3b}+6a^2b^2+4ab^3+b^4) \\ &= \dots + a\cdot\green{6a^2b^2} + b\cdot\blue{4a^3b} + \dots \\ &= \dots + (\green{6}+\blue{4})\red{a^3b^2} + \dots \\ \end{align} $$ In other words, the process of multiplying by $a+b$ combines the two numbers from the previous row of the triangle.

For any numbers $a$ and $b$, we have $$ \begin{align} (a+b)^n &= \binom{n}{0}a^n + \binom{n}{1}a^{n-1}b + \binom{n}{2}a^{n-2}b^2 + \dots \\ &+ \binom{n}{n-2}a^2b^{n-2} + \binom{n}{n-1}ab^{n-1} + \binom{n}{n}b^{n}. \end{align} $$ For example, $$ \begin{align} (a+b)^3 &= \binom{3}{0} a^3 + \binom{3}{1} a^2b + \binom{3}{2} ab^2 + \binom{3}{3} b^3 \\ &= a^3+3a^2b+3ab^2+b^3. \end{align} $$ This result is known as the binomial formula.

The binomial formula is often written as $$ (a+b)^n = \sum_{k=0}^n \binom{n}{k} a^k b^{n-k}. $$ Here the $\sum$ symbol denotes a sum. It means that you plug in all values $k=0,1,2,\dots,n$ and add the results, like this: $$ \binom{n}{0} a^0 b^{n-0} + \binom{n}{1} a^1 b^{n-1} + \dots + \binom{n}{n} a^n b^{n-n} $$ This is the same formula as above, except that $a$ and $b$ are swapped: instead of starting with $a^n$ and ending with $b^n$, it starts with $b^n$ and ends with $a^n$. This doesn't matter because $(b+a)^n$ is same as $(a+b)^n$.