So I was in class discussing the following problem:
We have $20$ different presents to distribute to $12$ children. It is not required that every child get something; it could even happen that we give all the presents to one child. In how many ways can we distribute the presents?
After some discussion we realized that the answer was $12^{20}$, because the problem could only be solved if we saw this from the perspective of the presents and not from the children. I thought it was very cool.
Then I went home and thought of a corollary to the problem: how many ways are there so that each child gets at least one present? I have been thinking for a week and I cannot solve it. I thought it was $12^{12} \times 12^8$, the first number to represent the presents distribute to at least one child and the other the ones spread out without discrimination. However, that number is bigger than the original number of ways which makes no sense. How would you go about solving this?
Best Answer
As you observed, there are $12^{20}$ ways to distribute the presents without restriction. There are $\binom{12}{k}$ ways to exclude $k$ of the recipients from receiving a present and $(12 - k)^{20}$ ways to distribute the presents to the remaining $12 - k$ people. By the Inclusion-Exclusion Principle, the number of ways to distribute the presents so that each person receives at least one is $$\sum_{k = 0}^{12} (-1)^k\binom{12}{k}(12 - k)^{20}$$