Binomial coefficients
This article introduces the Binomial Coefficients. It is best read with paper and pen so that you can have a go at the questions as you read.
There are several ways of defining the binomial coefficients, but for this article we will be using the following definition and notation: \[n\choose k\] (pronounced “$n$ choose $k$”) is the number of distinct subsets of size $k$ of a set of size $n$. More informally, it's the number of different ways you can choose $k$ things from a collection of $n$ of them (hence $n$ choose $k$).
So:
-
${3 \choose 1} = 3$ because you can either pick the first thing, or the second thing, or the third thing.
-
Likewise, ${3 \choose 2} = 3$ because you can either take the first two, the first and the third, or the last two. Notice that the order you choose the things in is ignored.
Can you work out the following binomial coefficents?
- $4 \choose 1$
- $4 \choose 2$
- $5 \choose 2$
- $6 \choose 2$
You'll need to come up with a systematic method of making sure you've found all the ways of choosing. Does your method suggest to you any way of calculating the result directly?
Now go back to the definition in terms of choosing things, and see if you can work out why the following are true for all $n\ge 1$:
\[{n \choose 0} = {n \choose n} = 1 \] \[{n \choose 1} = {n \choose n-1} = n \]
This starts to suggest a pattern, in fact:
\[{n \choose k} = {n \choose n-k}\]
Can you justify this pattern from the definition?
Now let's write out the binomial coefficients in a grid:
| 0 | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|
| 0 | 1 | ||||
| 1 | 1 | 1 | |||
| 2 | 1 | 2 | 1 | ||
| 3 | 1 | 3 | 3 | 1 | |
| 4 | 1 | 4 | 6 | 4 | 1 |
Do these look familiar? They should do. This suggests the following rule:
\[{n \choose k} = {n-1 \choose k} + {n-1 \choose k-1}\]
Thinking back to your systematic method, can you explain this relation in terms of choosing things?
We can use this relation to calculate binomial coefficients, but it's not very efficient. You'll find yourself having to calculate more and more binomial coefficients the larger your $n$ and $k$. So let's try to find another formula, by thinking about the process of choosing:
-
Suppose you want to choose five things from a collection of twelve. How many choices do you have for the first thing? How many choices for the second? How many choices for the third, fourth, and fifth? How many choices does this give altogether?
-
The problem with the above method is that it counts 1,2,3,4,5 and 2,1,3,4,5 separately even though they are really the same choice. How many times do you count each choice? How can you eliminate them from your count?
Once you've come up with a formula, can you use it to justify the earlier results algebraically?
The connection with the binomial
I mentioned these were called binomial coefficients at the beginning of the article, but I haven't mentioned the binomial formula since. Well, the binomial formula is this:
\[(a+b)^n = \sum_{k=0}^n {n \choose k} a^k b^{n-k}\]
So they are literally just the coefficients of $a^k$ in the expansion of the $n^\textrm{th}$ power.
Thinking about $(a+b)^n$ as $(a+b)(a+b)(a+b)\dots(a+b)$ and expanding in the usual way, can you see how the choosing-from-sets definition is connected to this idea?
Extensions
These formulae all have justifications both in terms of choosing things and in terms of algebra. See if you can find one or the other (or both!):
\[\sum_{k=0}^{n-r} {n-k \choose r} = {n+1 \choose r+1}\]
\[\sum_{k=0}^n {n \choose k} = 2^n\]
\[\sum_{k=0}^n {n \choose k}^2 = {2n \choose n}\]