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*5*4*3*2=720 ways to pick; one gift left, and can be given to any of the 5 child, so 720*5=3600 ways
the right answer seem to be 1800, why? i can't understand it
Best Answer
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$$
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.
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.
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$$