# Simple combinations question

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 ﬁsh. How many diﬀerent 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?

-
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/… –  VelvetThunder Dec 14 '10 at 7:58

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.

-

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 ﬁsh), 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

-
Probably you meant indistinguishable ?! –  VelvetThunder Dec 14 '10 at 7:57
Of course. Thanks for the correction. –  Robert Smith Dec 14 '10 at 16:12