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.
$\endgroup$3 Answers
$\begingroup$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$.
$\endgroup$ 2 $\begingroup$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.
$\endgroup$ 2 $\begingroup$This explanation is excessively easy (for real beginners), but may look long-ish. Okay, first of all, this formula, as you know, is a changed form of this one $\frac{n\cdot(n-1)\cdot(n-2)\cdot...\cdot(n-(k-1))}{n!}$. Why? Because it's obvious from this:$$\frac{n\cdot(n-1)\cdot(n-2)\cdot...\cdot(n-(k-1))}{n!}\cdot\frac{(n-k)!}{(n-k)!}=\frac{n\cdot(n-1)\cdot(n-2)\cdot...\cdot(n-(k-1))\cdot[(n-k)(n-k-1)\cdot...\cdot1]}{n!\,(n-k)!}=\frac{n\cdot(n-1)\cdot(n-2)\cdot...\cdot(n-k+1))\cdot[(n-k)(n-k-1)\cdot...\cdot1]}{n!\,(n-k)!}=\frac{n!}{n!\,(n-k)!}$$Now let's make the first version of this formula crystal clear and intuitive for anyone who knows nothing about math. So we're gonna make this specific formula intuitive, crystal clear, and as easy as pie:$$\frac{n\cdot(n-1)\cdot(n-2)\cdot...\cdot(n-(k-1))}{n!}$$
For further simplification, let’s say, $n=10, k=4$ So we have:$$\frac{10\cdot(10-1)\cdot(10-2)\cdot(10-3)}{4!}$$
Now, let’s have ten numbers in a box which are $0\,1\,2...\,9.\quad$Now we are going to draw four numbers from this box one at a time (we are gonna draw four times or in four steps): When we draw a number for the first time, we have ten different outcomes or possibilities. Let’s say, we are going to investigate each of these 10 possibilities/options separately. Let’s say in the first possibility we drew number $0$. The second step in drawing numbers is to draw for the second time. So, for the already drawn number $0$ we will then have $9$ possibilities/options on the second draw. Altogether it is $9$ possibilities for drawing twice when the first draw was number $0$. Because for the first draw we had $10$ possibilities, the overall number of possibilities is $10\cdot9=90\,:$ $$01\,, 02\,, 03\,, ....,09$$$$10\,, 12\,, 13\,, ....,19$$$$20\,, 21\,, 23\,, ....,29$$$$30\,, 31\,, 32\,, ....,39$$.............................................(I’m skipping five lines here)$$90\,, 91\,, 92\,, ....,98$$This table gives us $90$ possibilities and it is in line with our simple reasoning. Now, we have to try to stretch our imagination and continue the process for the third draw of the remaining numbers in the box. After the first two draws, we have $90$ possibilities (or $90$ pairs of numbers) and for each of these possibilities $8$ numbers are still left in our box for us to continue drawing numbers. So, it’s not difficult to figure out that after the third draw, we’ll have $90\cdot8=720\,$possibilities. We can visualize it by turning each column in the table above into a separate table with $8$ columns. We are gonna have $9$ such tables as we had $9$ columns in the initial table, and we gonna add into each new table one of the eight remaining numbers from the box for each initial pair turning pairs into triplets. Let’s visualize one such table here, for example, for column 2 of the above table: $$02\,$$$$12\, $$$$21\, $$$$31\, $$.............................................(I’m skipping $5$ lines here!)$$91\,$$As we prepared our table (it’s just a column yet), we now simulate the third draw for it. (Here it is done for the second column of the initial table):$$021\,, 023\,, 024\,, ....,029$$ (note that we now have 8 columns)$$120\,, 123\,, 124\,, ....,129$$$$210\,, 213\,, 214\,, ....,219$$$$310\,, 312\,, 314\,, ....,319$$.............................................(I’m skipping $5$ lines here!)$$910\,, 912\,, 913\,, ....,918$$We don’t change the first two numbers or pairs, and all of our first two numbers or pairs are different (there are $90$ of them). We just add all possibilities on the third draw. Making $9$ more tables like this ($10$ lines x $8$ columns), we will cover of the possibilities and the overall number of our triplets is gonna be $90\cdot8=720\,$ because we turned each column into a table of 8 columns (we are adding $7$ columns more so there are $8$ columns in our new tables of triplets). Now it’s trivial to see that on the last (fourth) draw, we are gonna have $10\cdot9\cdot8\cdot7=5040\,$ possibilities and these are called permutations. Each possibility is different but sometimes numbers are the same -- only the order is different. Just take a look at the tables above to see that. For example, in the very first table we see two pairs $(09)$ and $(90)$. Okay, let’s first write an intuitive formula for $k$-permutations:$$n\cdot(n-1)\cdot(n-2)\cdot...\cdot(n-(k-1))$$.
The final step is to calculate how many repetitions we have in our drawn four numbers out of $10$. Well, we are gonna have $5040$ quadruplets with repetitions like these: $1234\,$, $2341$... For each unique quadruplet we have $4! =24$ possibilities to re-arrange the order. Why? Well, if we had only two numbers or a pair (instead of a quadruplet) we'd have only two possibilities in terms of different options accounting for order, e.g. $12$ or $21$ and so on for each pair. Now then, if we had triplets, such as $(123)$, we'd need to account for order by placing number $3$ into three different “slots” that numbers $12$ and $21$ have:$$ (\,)\; 1\; (\,)\; 2\;(\,)$$$$ (\,)\; 2\; (\,)\; 1\;(\,)$$In the first line we have three free slots and the same with the lower line. Altogether $6$ possibilities:$$ (3)\; 1\; 2\;(\,)\quad\quad (\,)\; 1\; (3)\; 2\;(\,)\quad\quad(\,)\; 1\; (\,)\; 2\;(3)$$$$ (3)\; 2\; 1\;(\,)\quad\quad (\,)\; 2\; (3)\; 1\;(\,)\quad\quad(\,)\; 2\; (\,)\; 1\;(3)$$Now, let’s count the number of “ordering” or “arrangements” in a quadruplet. Well, we have 6 triplets and each of them has four “slots”. So, it’s $6\cdot4=24$. We can extend this logic for any number. That’s why the factorial shows the number of possible arrangements. Okay. Back to our example with four numbers drawn from ten numbers in the box. We calculated $5040$ possible quadruplets of drawn numbers. But we have a lot of repetitions there. Some of our quadruplets have the same numbers in many different orders or arrangements. Well, for each specific four numbers we have $4!=24$ quadruplets which are different only in the way numbers are arranged. To eliminate all the repetitions for each quadruplet, we have to divide by $24$. Hence, we arrive at the formula of combinations. It is$$\frac{n\cdot(n-1)\cdot(n-2)\cdot...\cdot(n-(k-1))}{n!}$$For our example it is $\frac{10\cdot(10-1)\cdot(10-2)\cdot(10-3)}{4!}=210$
Hope such simplicity makes things crystal clear Later on I'll add permutations and combinations with repetitions.
$\endgroup$ 1
