1
$\begingroup$

For example, how come $4 \choose 3$ (from 4 dice, choose 3 to be the same) can relate to the list:

d, s, s, s
s, d, s, s
s, s, d, s
s, s, s, d

Where s = same number, and d = different number? Shouldn't this be a permutations problem?

  • 0
    Because you chose exactly 3 out of 4: you chose 3 spots out of the 4 for the same number $s$.2012-03-29
  • 0
    If you are making four-letter "words" where you have only two available letters, indeed you are counting permutations. But the "choose" symbol can be useful in counting for example the number of words that have three s and one d. There is no one universal tool for counting permutations.2012-03-29
  • 0
    Actually binomial coefficient don't relate to permutations (even in the high-school sense of that word) but to combinations, which is exactly what you have here.2012-03-29

1 Answers 1

1

Consider the number of permutations of $0$ and $1$ where there are $a$ $0$s and $b$ $1$s.

You have a total of $a+b$ spots and you select $a$ of them to place the $0$s. This amounts to $\binom{a+b}{a}$.

If you want to count as permutations, if the zeroes and ones were distinct, you would get $(a+b)!$ permutations.

But each permutation where they are not distinct, gives rise to $a! b!$ permutations where they are considered distinct.

Thus the total number of "not-distinct" permutations is $\frac{(a+b)!}{a!b!}$.

Since the total is the same, irrespective of how you count them, you have just proved that (assuming a combinatorial definition of the binomial coefficient)

$$\binom{a+b}{a} = \frac{(a+b)!}{a!b!}$$

See Also: What is the proof of permutations of similar objects?