Understanding the intuition behind n choose k, and never forgetting this formula again
This \(n\) choose \(k\), \({}_nC_k\) or \(\binom{n}{k}\) comes up all the time in probability, combinatorics and machine learning.
I started writing this post because I was tired of trying to remember the formula and forgetting it all the time. Going deeper into this concept was a lot of fun. I hope you enjoy it too.
I was tired of remembering a formula by heart instead of deeply understanding it.
What does it mean?
Imagine I toss a coin four times. How many distinct sequences involve exactly three heads and one tail?
If I have a series of four bits (e.g., \(0011\)), how many distinct sequences contain exactly three ones and one zero?
These are the questions that we can answer with \(\binom{n}{k}\). There are many definitions of \(\binom{n}{k}\), all drier than one another.
Like everything I do, I generally start by going to Wikipedia.
“In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem.” — Wikipedia
This does not really help us.
Imagine I have three fruits: an apple, a banana and an orange. Three choose two (\(\binom{3}{2}\)) answers the question: how many ways do I have to choose two items from these three items, without caring about the order?
The answer is three:
- Apple, orange
- Banana, orange
- Banana, apple
How many sequences of three bits have two ones and one zero? The answer is also three:
- \(011\)
- \(110\)
- \(101\)
We can look at the last example as a binary tree:
The question we asked above could be framed as: how many paths involve two ones and one zero?
Here we choose which two of the three positions contain ones. Different choices of positions give different sequences.
Why does it matter?
But why do we need to know \(\binom{n}{k}\)? If it is just to count heads, tails and bits, we could do without.
Now, let’s say you are living with your partner and decide who takes the bins out based on the outcome of a coin toss. In the case of heads, you go; tails, your partner. In four of the last five tosses, the coin landed on heads.
Getting a bit tired of carrying the bins down the five floors of an old Berlin building with no lift, you may start to wonder: with a fair coin, with equal probabilities of heads and tails, what would be the probability of this happening?
We can start answering with a simpler example. What is the probability of having two heads out of two independent coin tosses? To do so, we can draw a binary tree, count the paths with two heads and sum their probabilities.
There is only one path with two heads for two coin tosses. Its probability with a fair coin is \(0.5 \cdot 0.5 = 0.25\). Easy, and a reasonably unlucky draw.
Now, let’s compute the probability of exactly four heads out of five tosses. The binary tree gets much bigger:
And counting becomes trickier:
There are five paths with four heads out of five tosses. Each of these has the same probability. To get the probability of exactly four heads out of five tosses, we need to compute the probabilities of each path and add them up. All these paths have the same probability:
\[ p_{\text{head}}^4 \cdot p_{\text{tail}}^1 = 0.5^4 \cdot 0.5^1 = \frac{1}{32} = 0.03125. \]
Multiplying this by five, we get:
\[ 5 \cdot \frac{1}{32} = \frac{5}{32} = 0.15625 = 15.625\%. \]
This shows the limits of our counting approach. The binomial coefficient and the binomial distribution give us a better way. To get the probability of exactly \(k\) successes, each with probability \(p\), out of \(n\) independent trials with the same success probability (e.g., \(k=4\) heads, \(p=0.5\) for our fair coin, and \(n=5\) coin tosses), we can use the following formula, where \(X\) counts the successes:
\[ P(X=k) = \binom{n}{k} \cdot p^k \cdot (1-p)^{n-k}. \]
This may look scary, but this is exactly what we did to compute the probability of four heads out of five coin tosses:
\[ \binom{5}{4} \cdot 0.5^4 \cdot 0.5^1 = 5 \cdot \frac{1}{32} = \frac{5}{32} = 15.625\%. \]
But what if we have to compute \(\binom{100}{76}\)? The binary tree could get quite big:
The illustration stops after ten levels. The full tree would have \(2^{100} \approx 1.27 \cdot 10^{30}\) endpoints.
Unless you enjoy this kind of task, counting is not an option.
The big formula
Thankfully, \(\binom{n}{k}\) can be computed directly with a big scary formula, for integers \(0 \leq k \leq n\):
\[ \binom{n}{k} = \frac{n!}{k! \cdot (n-k)!}. \]
As a reminder, for a positive integer \(n\):
\[ n! = n \cdot (n-1) \cdot \ldots \cdot 2 \cdot 1. \]
\[ 3! = 3 \cdot 2 \cdot 1 = 6. \]
And \(0! = 1\). This one confused me for a while too: the topic of another article. For now, believe me.
You can try this formula out with \(\binom{2}{2}\) and \(\binom{5}{4}\), which we already calculated:
\[ \binom{2}{2} = \frac{2!}{2! \cdot 0!} = \frac{2}{2 \cdot 1} = 1. \]
\[ \binom{5}{4} = \frac{5!}{4! \cdot 1!} = \frac{5 \cdot 4!}{4! \cdot 1} = 5. \]
If you want to have any chance of remembering it, you have two options:
- Anki-style spaced repetition systems (yay, loving life)
- Understanding where this formula comes from
Getting some intuition back
Let’s get back to counting the number of heads (denoted by \(1\), and tails by \(0\)) in a sequence of four coin tosses. Imagine the following sequence:
\[ 0,0,1,1. \]
Let’s imagine that we care about the order and that all of these are unique:
\[ 0_1, 0_2, 1_3, 1_4. \]
We would have \(4!\) (or \(n!\) more generally) ways to order these four unique elements.
I have the choice of four elements for the first position, three for the second one, two for the third one and one for the last:
\[ 4 \cdot 3 \cdot 2 \cdot 1 = 24. \]
If these elements are not unique, then the following two strings should be equivalent:
\[ (0_1, 0_2, 1_4, 1_3) \quad \text{and} \quad (0_1, 0_2, 1_3, 1_4). \]
The count \(n!\) overcounts as it treats all elements as unique. We can correct this by dividing \(n!\) by the \(k!\) ways we can order the ones and the \((n-k)!\) ways we can order the zeros. Each distinct bit sequence is counted \(k! \cdot (n-k)!\) times. See what I did there? We can get back to our formula:
\[ \binom{n}{k} = \frac{n!}{k! \cdot (n-k)!}. \]
In our four-toss example, this gives \(\binom{4}{2} = 24/(2 \cdot 2) = 6\) distinct sequences.
Mindblown.
Final thoughts
The \(\binom{n}{k}\) formula comes up everywhere: probability, mathematics and even in my latest article on SHAP value calculations. It is the type of formula that is very easy to forget if we do not truly understand where it comes from.