[Math] Combinatorics: Distributing different toys

combinatorics

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$.

Best Answer

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.