I'm home for winter break, which has meant long morning walks - inspired (a little) by Roger Penrose. On today's walk I decided to try deriving the formula for ${n \choose k}$.

$n$ choose $k$ is a formula I never actually learned to derive. It was simply another thing to memorize in high school. I wanted to see if I could work it out from scratch. Of course, I immediately recalled the familiar-looking formula

Taking this as given, how do we work backwards to see, cleanly, why it counts the number of distinct ways to choose $k$ items from a set of $n$?

The numerator is $n!$,A disclaimer: most of what I'll say next is probably trivial. I'm going to talk about it as if it isn't, to walk through how I thought about this. There will likely be parts that are over-explained. which we know is the number of ways to order $n$ items. This seems odd - we're trying to count selections, not orderings.

How does that relate to choosing $k$ items?

It turns out there's an equivalent framing that makes the $n!$ sensible. Take an ordering of all $n$ items, and declare that the "chosen" items are simply the first $k$ items in the ordering. The remaining $n-k$ are "not chosen." Now every permutation of $n$ items induces a choice.

Now we're overcounting, in two ways. First, we don't care how the unchosen $n-k$ items are ordered among themselves - that's $(n-k)!$ redundant arrangements. Second, we don't care how the chosen $k$ items are ordered either - that's $k!$ more. Dividing by both gives us

Why does dividing actually work? Think of it this way: each distinct selection of $k$ items corresponds to exactly $(n-k)!\cdot k!$ different orderings - all the ways to permute the chosen and unchosen items among themselves. Since every ordering falls into exactly one such group, and all groups are the same size, dividing the total count by the group size gives us the number of distinct selections:

⁂

After working through the permutation argument, I had the slightly annoying realization that I'd taken the long way around. It turns out there's a nicer version of the ${n \choose k}$ formula, which is (in my opinion) more intuitive.

Notice:

So we can rewrite

Why is this nicer? The numerator now has a direct interpretation: it's simply the number of ways to choose $k$ items in order.This numerator is called a falling factorial, sometimes written $(n)_k = n(n-1)\cdots(n-k+1)$. Pick the first item: $n$ choices. Pick the second: $n-1$ remain. And so on, until you've made $k$ picks. This is probably what you'd first write down if you tried to derive ${n \choose k}$ from scratch.

Of course, you are still overcounting here. Specifically, a single set of $k$ items gets counted many times, once for each order you could have picked those same items in. There are exactly $k!$ such orders, so dividing by $k!$ is what removes the ordering.

⁂

It's curious that I was never taught the intuitive formula $\frac{n(n-1)\cdots(n-k+1)}{k!}$, which would have made a lot more sense to me than the symmetric version. The falling factorial directly represents "choosing $k$ items in order," and dividing by $k!$ removes the ordering. However, the symmetric form $\frac{n!}{(n-k)!k!}$ is actually more useful for proofs, e.g. it's immediately obvious that ${n \choose k}={n \choose n-k}$.

Hopefully the formula makes more sense now (if it didn't before)!