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
    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?