Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Because you chose exactly 3 out of 4: you chose 3 spots out of the 4 for the same number $s$. –  N. S. Mar 29 '12 at 2:13
    
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. –  André Nicolas Mar 29 '12 at 2:15
    
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. –  Marc van Leeuwen Mar 29 '12 at 12:28

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.