In how many ways can six different gifts be given to five different children with each child receiving at least one gift and each gift being given to exactly one child?
My Answer:
For each child to pick from $6$ different gifts, there are $6\times5\times4\times3\times2=720$ ways to pick; one gift left, and can be given to any of the $5$ child, so $720\times5=3600$ ways.
The right answer seem to be $1800$, why? I can't understand it.
On
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: 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$$
On
First, assign each gift either to a child, with the last gift being a bonus gift. This can be done in 6! ways. Now decide who gets the bonus gift. This can be done in 5 ways.
But you don't want to tell the children which gift is normal and which gift is bonus, so divide out the overcount of 2. Thus the final answer is $6!\cdot5/2=1800.$
On
You are looking for the number of surjections from a set with six elements into a set with five elements. According to the Twelvefold way this is $$5!\left\{{6\atop5}\right\}=120\cdot15=1800$$ where the expression in brackets represents a Stirling number of the second kind.
It's because you double-count: there is one child that ends up with two gifts, and there are two ways that can happen with your method: first the child gets gift $A$, and gift $B$ was the 'leftover' gift, or vice versa.