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.

Justin needs to pick 17 toy animals to give to children at a party. The animals come in 5 kinds: dogs, dinosaurs, cows, lizards, and fish. How many different ways can he choose his set of toys

Ok the answer for this is 21 choose 4. However, I dont understand how they arrived at this answer. If there are 17 slots, and for each slot, you can choose between 5 animals, then you should have $5^{17}$. Where has my reasoning gone wrong?

share|improve this question
1  
Presumably you cannot distinguish between 2 dogs, between 2 dinosaurs, etc. Your method counts dog-dog-dog-dog-dinosaur as distinct from dog-dinosaur-dog-dog-dog.. –  Jonas Meyer Dec 14 '10 at 1:35
    
There is something missing from this question; where is the 21 coming from? –  Hans Parshall Dec 14 '10 at 1:42
    
It says: 17+5-1 choose 5-1 –  maq Dec 14 '10 at 1:43
    
Zaricuse made it clear below, sorry. –  Hans Parshall Dec 14 '10 at 1:46
    
Check out Sivaram's explanation here: math.stackexchange.com/questions/11468/… –  Quixotic Dec 14 '10 at 7:58

2 Answers 2

up vote 4 down vote accepted

As Jonas Meyer indicated, the way you counted will include separately different orderings of the same numbers of each animal.

Instead, you can have 21 slots. Four slots are to be filled with "dividers". You put dogs to the slots (if any) to the left of divider 1, dinosaurs in slots (if any) between divider 1 and divider 2, and so on until you place fish to the right of the 4th divider. There are ${\displaystyle {21 \choose 4}}$ ways to place the four dividers, and each placement of the four dividers corresponds to exactly one way of choosing the number of each animal brought to the party.

share|improve this answer

Following the advice from Jonas, there are $A_{r,n}=\displaystyle \binom{n+r-1}{r}$ ways to obtain indistinguishable distributions where each distribution is described in terms of n-tuples $(r_{1},...,r_{n})$ satisfying $$r_{1}+r_{2}+...+r_{n}=r$$

In your particular problem, you want to enumerate the number of solutions for the equation $$r_{1}+r_{2}+...+r_{5}=17$$ where $r_{i}$ represents the number of elements contained in a box/cell labeled as $i$ where $i=1=\text{dogs}$, $i=2=\text{dinosaurs}$,..., $i=5=\text{fishes}$. For example, one such a way is to pick $(17,0,0,0,0)$ (say, 17 dogs and nothing else), other choice would be $(13,1,1,1,1)$ (13 dogs, 1 dinosaur, 1 cow, 1 lizard and 1 fish), etc.

Therefore, you have $\displaystyle \binom{5+17-1}{17}$ which is equivalent to $\displaystyle \binom{21}{4}$.

Reference: Feller. An Introduction to Probability Theory and Its Applications. Chapter II.5

share|improve this answer
    
Probably you meant indistinguishable ?! –  Quixotic Dec 14 '10 at 7:57
    
Of course. Thanks for the correction. –  Robert Smith Dec 14 '10 at 16:12

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.