# Combinatorics: Distributing different toys

Find the number of ways in which $6$ different toys may be distributed among $4$ children so that each child gets at least $1$ toy.

The problem is simple enough, I only need to verify my solution.

Initially I select $4$ toys out of $6$. This can be done in $\binom{6}{4}$ ways. These can be distributed in $4!$ ways. Now I have $2$ toys left to be distributed to $4$ children. For every toy, I have $4$ options, hence this can be done in $4^2=16$ ways.

So in all, I have $\binom{6}{4} \times 4! \times 16 = 5760$.

-
Your solution is correct. A slightly different way would be to first give a toy to each child: 6 choices for the first child, then 5 possibilities for the second, and so on for a total of (6)(5)(4)(3) ways. Then of the two toys remaining, there are 4 possible recipients for each, giving (6)(5)(4)(3)(4)(4) = 5760 possibilities, as you found. – Rick Decker Jun 6 '12 at 17:47
Thanks Rick, much appreciated. – Karan Jun 6 '12 at 17:50
– woz Jun 6 '12 at 17:53
Answer seems too large (see solutions below). Your overcount stems from the fact that if kid a gets toy 1 first (in the 'choose 4' step) then toy 6 or gets toy 6 first then toy 1, these are the same outcomes (yet you count these more than once). – John Engbers Jun 6 '12 at 18:06

The solution is not correct. As an illustration, let us distribute $5$ toys instead. Let us solve this simpler problem using the argument of the post. That procedure would suggest a count of $\binom{5}{4}(4!)(4)=480$.

Now let us count the actual number of ways to distribute the $5$ toys. Some kid will get $2$ toys, the rest will get $1$ each. The lucky kid can be chosen in $4$ ways. For each of these ways, the toys she gets can be chosen in $\binom{5}{2}$ ways. And for each of these ways, the rest of the distribution can be done in $3!$ ways, for a total of $240$.

Remark: For $6$ toys, the answer turns out to be $1560$. Note that there is no simple "overcount ratio."

In general, the number of ways to distribute $n$ toys among $k$ children so that each gets at least one toy is $k!S(n,k)$, where $S(n,k)$ is the Stirling number of the second kind.

There are nice recurrences that make computing the Stirling numbers of the second kind not too hard, at least for small inputs. Also, a number of programs will do the job. Wolfram Alpha does it for free. Just type in $S2(6,4)$.

Added: There is a simple way to see that $5760$ cannot be correct. Let us count the number of ways to split the $6$ toys between the $4$ kids, with no restrictions. So one or more kids may get nothing. Line up the toys in ascending order of desirability. The worst toy can be assigned in $4$ ways. For each of these, the second worst can be assigned in $4$ ways, and so on, for a total of $4^6=4096$. This is less than $5760$!

This beginning, together with the Principle of Inclusion/Exclusion, can be used to count the number of ways to distribute the toys so that each kid gets at least one toy.

For a quick and dirty count for $6$ toys and $4$ kids, we use the method that was illustrated earlier for $5$ toys and $4$ kids.

Maybe (i) a kid gets $3$ toys, and the rest get $1$ each or (ii) two kids get $2$ toys each, and the rest get $1$ each.

Counting the patterns in (i) is easy. The lucky kid can be chosen in $4$ ways. For each way, the toys she gets can be chosen in $\binom{6}{3}$ ways. And now the remaining toys can be distributed in $(3)(2)(1)$ ways, for a total of $480$ ways of type (i).

Counting the patterns in (ii) is tricky, just like counting the number of "two pair" poker hands is tricky. The two lucky kids can be chosen in $\binom{4}{2}$ ways. For each of these ways, the toys for the younger of the two lucky kids can be chosen in $\binom{6}{2}$ ways. And now the toys for the other lucky kid can be chosen in $\binom{4}{2}$ ways. Finally, the rest of the toys can be assigned in $(2)(1)$ ways. The total number of ways of type (ii) is $1080$.

This gives $1560$ as the number of ways to do the distribution.

-
For 6 toys using your method, some kid may get 2 toys (4*1 choices for choosing this kid) or 2 kids get 1 toy each (4*3 choices for choosing 2 kids). The remaining 4 toys can be arranged in 4! ways in both cases. Two toys can be chosen in 6C2 ways. So in all, i get 6C2*4!{4*1 + 4*3} = 5760. What did i overcount in this calculation? – Karan Jun 10 '12 at 10:28
"My" method does not give $5760$. I have added details for $6$ to the post. Too awkward for a comment, comments are too short, editing facilities not good. I have also added material on why $5760$ is absolutely impossible. – André Nicolas Jun 10 '12 at 15:18