In how many ways can six different gifts be distributed to five children if each child receives at least one gift?
Method 1: Since each child receives a gift and there are six gifts to give to five children, one child must receive two gifts. There are five ways to choose which child receives two gifts and $\binom{6}{2}$ ways to choose which two of the six gifts are given to that child. The remaining four gifts must be distributed to the remaining four children in $4!$ ways. Hence, the number of ways the gifts can be distributed so that each child receives at least one gift is
$$\binom{5}{1}\binom{6}{2}4!$$
Method 2: We use the Inclusion-Exclusion Principle. There are five possible recipients for each of the six gifts. Thus, without the restriction that each child receives a gift, we could distribute the gifts in $5^6$ ways. There are $\binom{5}{k}$ ways to exclude $k$ of the children from receiving a gift and $(5 - k)^6$ ways to distribute the six gifts to the remaining $5 - k$ children. By the Inclusion-Exclusion Principle, the number of ways we can distribute the gifts is
$$\sum_{k = 0}^{5} (-1)^k\binom{5}{k}(5 - k)^6$$
Where did you go wrong?
You counted each distribution twice, once for each way you could designate one of the two gifts the child who receives two presents gets as the additional gift. Say Amanda receives both a ball and a bicycle, while the other children each receive one gift. You count this scenario twice, once when you first give Amanda the ball and then give the bicycle as the additional gift and once when you give Amanda the bicycle and then give the ball as the additional gift.
You asked the following question in the comments: In how many ways can seven different gifts be distributed to five children if each child receives at least one gift?
Method 1: Since there are seven gifts and each of the five children receives at one least one gift, there are two possibilities:
- One child receives three gifts and each of the other four children receive one gift.
- Two children each receive two gifts and each of the other three children receive one gift.
One child receives three gifts and each of the other four children receive one gift: There are five ways to choose the child who receives three gifts and $\binom{7}{3}$ ways to choose which three of the seven gifts that child receives. The remaining four gifts can be distributed to the remaining four children in $4!$ ways. Hence, there are
$$\binom{5}{1}\binom{7}{3}4!$$
such distributions.
Two children each receive two gifts and each of the other three children receives one gift: There are $\binom{5}{2}$ ways to choose which two of the five children receive two gifts. There are $\binom{7}{2}$ ways to choose which two of the seven gifts will be given to the younger of these two children and $\binom{5}{2}$ ways to choose which two of the remaining five gifts will be given to the older of these two children. The remaining three presents can be distributed to the remaining three children in $3!$ ways. Hence, there are
$$\binom{5}{2}\binom{7}{2}\binom{5}{2}3!$$
such distributions.
Total: Since the two cases are mutually exclusive and exhaustive, the number of ways seven different gifts can be distributed to five children so that each child receives at least one gift is
$$\binom{5}{1}\binom{7}{3}4! + \binom{5}{2}\binom{7}{2}\binom{5}{2}3!$$
Method 2: We use the Inclusion-Exclusion Principle. If we replace $6$ by $7$ throughout the argument given in the first problem, we obtain
$$\sum_{k = 0}^{5} (-1)^k\binom{5}{k}(5 - k)^7$$
ways to distribute seven distinct gifts to five children so that each child receives at least one gift.
In how many ways can $m$ different gifts be distributed to $n$ children if each child receives at least one gift?
This is only possible when $m \geq n$. Since there are $n$ possible recipients for each of the $m$ gifts, there are $n^m$ ways to distribute the gifts without restriction. There are $\binom{n}{k}$ ways to exclude $k$ of the $n$ children from receiving a gift and $(n - k)^m$ ways to distribute the $m$ gifts to the remaining $n - k$ children. By the Inclusion-Exclusion Principle, the number of ways the $m$ gifts can be distributed to $n$ children so that each child receives at least one gift is $$\sum_{k = 0}^{n} (-1)^k\binom{n}{k}(n - k)^m$$
Best Answer
See we have infinite supply for each present . Now let us take a child A then take one present we can either give it or not give it. So for each present we have two ways . There are such 20 presents so for a single child so you have $2×2×\cdots (\text {20 times}) =2^{20} $ ways. This is for one child we have 12 such children thus the answer is $(2^{20})^{12} $