How to understand the combination formula?

I'm reading an algorithm book. In which it mentioned:

Imagine (once again) you have n people lined up to see a movie, but there are only k places left in the theater. How many possible subsets of size k could possibly get in? That’s exactly $C(n,k)$, of course, and the metaphor may do some work for us here. We already know that we have $n!$ possible orderings of the entire line. What if we just count all these possibilities and let in the first $k$? The only problem then is that we’ve counted the subsets too many times. A certain group of k friends could stand at the head of the line in a lot of the permutations; in fact, we could allow these friends to stand in any of their $k!$ possible permutations, and the remainder of the line could stand in any of their $(n–k)!$ possible permutations without affecting who’s getting in. Aaaand this gives us the answer!

$$C(n,k)= \frac{n!}{k!(n −k)!}$$

This formula just counts all possible permutations of the line (n!), and divides by the number of times we count each “winning subset,” as explained.

I'm not quite understand why the reminder can in any $(n-k)!$ permutation, if he stands at the end of the queue, won't he let all these people in? And why I should use $n!$ to divide by $k!(n-k)!$ ? Didn't see that consequence from the metaphor.

If you have better ideas to explain this formula, you can use them of course.

Solution 1:

The explanation of the formula is quite nice, I think. First, it says that there are $n!$ different reorderings of the row of $n$ people. Now, say I want to choose a set of $k$ people out of the $n$ people. I choose it by choosing the first $k$ people in the row.

Now, take one particular set of $k$ people. Let's call the people in the set chosen and the others unchosen. How many different reorderings of the row caused this exact set of chosen people to be selected? I know that if they are selected, all these $k$ people were in the first $k$ places, and all the rest were in the remaining $n-k$.

Well, there are $k!$ possible reorderings of the people on the first $k$ places, so for each ordering of the unchosen people in the $n-k$ unchosen places, there are $k!$ reorderings of the chosen people in which all the chosen occupy the first $k$ places. But there are $(n-k)!$ reorderings of the unchosen people, and for each of them, $k!$ reorderings of the chosen ones, so all together $k! (n-k)!$ such orderings in which the chosen ones get selected.

So, out of all $n!$ reorderings of all people, one particular set of size gets chosen $k!(n-k)!$ times. Since in each choosing, I choose one set, there must therefore be $\frac{n!}{k!(n-k)!}$ different sets of size $k$.

Solution 2:

We can think about the binomial coefficient as a number of ways to split a set that contains $n$ elements into two subsets that contain $k$ and $n-k$ elements.

Consider this very simple example. Suppose that we have a set $\{a,b,c\}$ and we want to split this set into two subsets with $1$ and $2$ elements. The possible subsets are as follow: $\{a\}$ and $\{b,c\}$, $\{b\}$ and $\{a,c\}$, $\{c\}$ and $\{a,b\}$. The number of ways to form two subsets is $3$.

Following the given example, we first would consider all the orderings of this set (the number of such orderings is $3!=6$) and then we would put the first element into the first subset and the remaining elements into the second subset. We would obtain the following subsets: $\{a\}$ and $\{b,c\}$, $\{a\}$ and $\{c,b\}$, $\{b\}$ and $\{a,c\}$, $\{b\}$ and $\{c,a\}$, $\{c\}$ and $\{a,b\}$, $\{c\}$ and $\{b,a\}$. But $\{b,c\}$ and $\{c,b\}$ are the same subsets because the order does not matter. So we must divide the number of the orderings by the number of ways we can order the elements in the second subset. So we obtain that $$ C(3,1)=\frac{3!}{1!2!}=3. $$

In general, $$ C(n,k)=\frac{n!}{k!(n-k)!}. $$

I hope this simple example helps.