Santa has to deliver 21 presents to 7 distinguishable children. Among the 21 presents are 7 indistinguishable action figures, 7 indistinguishable basketballs, and 7 indistinguishable construction toys. Santa must distribute these presents in such a way that all the presents are distributed and no child gets more than two of the same type of present. However, he is allowed to give no presents to a child if he so wishes.
If the number of ways that Santa can distribute the presents is equal to where is a positive integer, find
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Santa can distribute the three kinds of toys independently. The number of ways is therefore a 3 , where a is the number of ways one type of toy can be distributed.
In principle, seven indistinguishable toys may be divided among seven distinguishable children in ( 6 7 + 6 ) = 1 7 1 6 ways. (A simple star-and-bar argument.)
However, we now have counted several ways in which three or more of the toys go to one child. Consider therefore the situations in which three of the toys are given to one particular child (7 choices here). The remaining 4 toys can be divided in ( 4 4 + 6 ) = 2 1 0 ways. Thus we subtract 7 × 2 1 0 = 1 4 7 0 situations where one child gets too many toys.
But note that we have subtracted too much now; if two children received three or more toys, that situation has been subtracted twice. We make up for this by adding back in the situations where two children ( ( 2 7 ) = 2 1 choices) get three of the gift each; the remaining 1 toy can be assigned to 7 children. Thus we add back in 7 × 2 1 = 1 4 7 ways.
The solution, then, is a = 1 7 1 6 − 1 4 7 0 + 1 4 7 = 3 9 3 .