# Why does $\binom{10}{7} = \frac{10!}{(10-7)!7!}$

We just learned that: $\dbinom{10}{7}= \frac{10 \times 9 \times 8 \times 7 \times 6 \times 5 \times 4}{7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1}$, so that:

If you throw a dice 10 times, the probability of getting $6$, $7$ of the times is: $\dbinom{10}{7} \times {\frac{1}{6}}^7 \times {\frac{5}{6}}^3$, because $\dbinom{10}{7}$ will give us the number of different ways you can get $7$ "correct" out of $10$.

I wonder why this works. Why does $\dbinom{10}{7}$ work as it does? (In my search I stumbled upon this way of writing it: $\dbinom{10}{7} = \frac{10!}{(10-7)!7!}$. It is a little bit different, but maybe it is more correct?

-
What exactly do you intend to ask? could you be more specific, and that link to purplemath(funny?) site doesnt work –  Tomarinator May 14 '12 at 14:04
I suppose the question is about the binominal coefficient? –  Johannes Kloos May 14 '12 at 14:06
10C7 can be written as (10x9x8x7x6x5x4)/(7x6x5x4x3x2x1) to find how many ways 7 "correct" can happen out of 10 trials. But, why? Why can you write it like that? It's a poor example, but 5^2x5^3=5^3+2=5^5 because 5x5 x 5x5x5 = 5^5... X^n x X^m = X^n+m. It's a rule that works, but why does this rule about 10C7 work? –  Friend of Kim May 14 '12 at 14:09
@50ndr33: You're supposed to use $\LaTeX$, it's not easy to follow otherwise. –  Gigili May 14 '12 at 14:11
@Gigili Sorry, but I don't know LaTeX... –  Friend of Kim May 14 '12 at 14:12

This is quite difficult to communicate with text, but I will try. It's important to understand each point in turn, as each one follows from the previous one. Please comment if you have any questions about anything that isn't clear:

1. First, think about how many ways there are to arrange ABCDE? Perhaps it's clear that there are $5\times 4\times 3\times 2\times 1 = 5! = 120$ permutations? If not, we could maybe start with a shorter example, like ABC.

2. So then (once you've understood the first point!), how many ways are there to arrange AACDE? Well, there are still $5! = 120$ permutations. But, some of these arrangements are the same. In fact, we are double counting, because the two A-s can appear in either order. So, in fact there are $5!/2 = 60$ combinations.

3. How many ways are there to arrange AAADE? There are still $5! = 120$ permutations, but now each arrangement is counted 6 times. Because there are $3! = 6$ ways to arrange the A-s. So, there are $5!/3! = 20$ combinations.

4. How many ways are there to arrange AAADD? There are still $5! = 120$ permutations, but there are 6 ways to arrange the A-s (six-times-counting), and 2 ways to arrange the D-s (double counting). In fact, each distinct arrangement is now counted $6\times 2 = 12$ times. In other words, there are $5!/(3!2!)$ combinations here.

5. Whether we are interested in permutations or combinations depends on whether we care about the order of the results. If we are just counting the number of 6s, we don't care about the order, we just care about how many 6s we got. So, we should check the combinations.

6. If you call A the result of getting a 6, and B the result of getting anything other than a 6, then we are trying to find the number of combinations of A-s and B-s, as in part 4 above. We can extend this idea to any number, like 10 dice and counting 7 sixes.

Hopefully it's clear how this leads to the idea of a binomial coefficient?!

-
Normally, I wouldn't spam with a comment that is of no use. But this time I have to! This is a GREAT answer! This deserves +2! –  Friend of Kim May 14 '12 at 18:22
Thanks :) I'm happy that you were helped by this answer. –  Ronald May 14 '12 at 23:02

I wrote the answer below while you were still editing your post, and realized after I'd finished writing it that I may have missed the point of your question. My answer was intended as an explanation for the presence of the $\binom{10}{7}$ factor in the formula for the probability of tossing exactly seven 6s in 10 tosses. Looking at your revised post, it seems that your real question may be about why $\binom{10}{7}$ is computed the way that it is. I'll try to answer this second question below.

The purpose of the $\binom{10}{7}$ factor is to count the number of different orders in which the seven 6s and three non-6s might occur in 10 tosses.

Let's take a smaller example: the probability of tossing exactly three 6s in five tosses is $\binom{5}{3}\cdot\left(\frac{1}{6}\right)^3\left(\frac{5}{6}\right)^2$. The factor $\binom{5}{3}=10$ is the number of sequences of tosses containing exactly three 6s and two non-6s. Let 'N' stand for non-6. Then these ten sequences are

666NN
66N6N
66NN6
6N66N
6N6N6
6NN66
N666N
N66N6
N6N66
NN666.

Each of the listed sequences has probability $\left(\frac{1}{6}\right)^3\left(\frac{5}{6}\right)^2$ of occurring, so the total probability of tossing three 6s is $\left(\frac{1}{6}\right)^3\left(\frac{5}{6}\right)^2+\left(\frac{1}{6}\right)^3\left(\frac{5}{6}\right)^2+\ldots+\left(\frac{1}{6}\right)^3\left(\frac{5}{6}\right)^2$ (the sum contains $\binom{5}{3}$ terms). This yields $\binom{5}{3}\cdot\left(\frac{1}{6}\right)^3\left(\frac{5}{6}\right)^2$ as the probability.

To see why $\binom{5}{3}$ gives the correct number of sequences, observe that each of the sequences is specified by choosing, from the five available positions, which three will contain 6. We also need to choose two positions for the Ns, but once the positions of the 6s have been chosen, there are only two positions left to choose from. Hence there are $\binom{5}{3}\cdot \binom{2}{2}=\binom{5}{3}$ ways of making these choices (since $\binom{2}{2}=1$). To give a concrete example of how the selection process above results in a sequence: the sequence 6N66N would be formed if the set $\{1,3,4\}$ were chosen for the positions of the 6s, leaving $\{2,5\}$ as the set of positions for the Ns.

Explanation for computation of $\binom{10}{7}$: The expression $\binom{n}{r}$ (read '$n$ choose $r$') equals the number of subsets of size $r$ that can be selected from a set of size $n$. This was used above when we computed the number of ways of selecting a set of three positions from a set of five possible positions. You note that $$\binom{10}{7}=\frac{10\cdot9\cdot8\cdot7\cdot6\cdot5\cdot4}{7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1},$$ and ask whether the formula $\binom{10}{7}=\frac{10!}{(10-7)!7!}$ is more correct. In fact, both are correct. The latter can be rewritten as $\frac{10!/(10-7)!}{7!}$, which matches up with the former, since both the numerators and the denominators in the two expressions coincide. To see that the numerators coincide: \begin{aligned} 10!/(10-7)!=10!/3!&=\frac{10\cdot9\cdot8\cdot7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1}{3\cdot2\cdot1}\\ &=\frac{10\cdot9\cdot8\cdot7\cdot6\cdot5\cdot4\cdot(3\cdot2\cdot1)}{3\cdot2\cdot1}\\ &=10\cdot9\cdot8\cdot7\cdot6\cdot5\cdot4. \end{aligned} This numerator is the number of ways of placing seven items chosen from a set of 10 into seven slots and is denoted $\,_{10}P_7$: there are 10 items that might fill the first slot, 9 that might fill the second slot, and so on, ending with 4 items that might fill the seventh slot. Since we are trying to count the number of ways to select seven items, but don't care about arrangement of the selected items, this massively overcounts: for each selection of seven items we are counting all of the $7!$ possible orders in which those items could have been drawn. To eliminate this overcounting, we divide by $7!$: $\binom{10}{7}=\frac{\,_{10}P_7}{7!}$.

Incidentally, you may have noticed that in your first formula for $\binom{10}{7}$, both numerator and denominator contain the factor $7\cdot6\cdot5\cdot4$, which means that we may cancel this factor, leaving $\binom{10}{7}=\frac{10\cdot9\cdot8}{3\cdot2\cdot1}=\frac{\,_{10}P_3}{3!}=\binom{10}{3}$. In fact, $\binom{n}{r}$ always equals $\binom{n}{n-r}$, and it is a nice shortcut to take the smaller of $r$ and $n-r$ when computing $\binom{n}{r}$.

This equality can be proved algebraically by inspecting your second formula $\binom{n}{r}=\frac{n!}{(n-r)!r!}$ and asking what happens when $r$ is replaced by $n-r$. (Nothing, in fact, changes, except for the order of the factors in the denominator.) A more conceptual explanation is that the number of ways of selecting seven items from 10 (and hence of leaving three items behind) is the same as the number of ways of selecting three items from 10 (and hence of leaving seven items behind).

-