I'm giving out 100 identical candies to 5 kids. The two youngest kids want at most 1 piece. The middle kid will take any number of pieces. The two oldest kids, Calvin and Lin, both demand an odd number of pieces. In how many ways can I distribute the candy?
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.
Casework would seem kind of messy. So instead we will try to make a generating function.
The generating function for the youngest two kids are : ( 1 + x ) 2
because they only want zero or one candy.
The generating function for the middle kid is: 1 + x + x 2 + . . .
because he is fine with any number of candy.
The generating function for Calvin and Lin are: x + x 3 + x 5 + . . . ) 2
since they only want an odd number of candy.
Therefore the number of ways to distribute the 100 candies is equivalent to the coefficient of the x 1 0 0 term of:
( 1 + x ) 2 ( 1 + x + x 2 + . . . ) ( x + x 3 + x 5 + . . . ) 2 = ( 1 − x ) ( 1 − x 2 ) 2 x 2 ( 1 + x ) 2
= ( 1 − x ) 3 x 2 = x 2 ∑ k = 0 ∞ ( 2 k + 2 ) x k
It is easy to see that the x 1 0 0 term coefficient is just the x 9 8 term coefficient of ∑ k = 0 ∞ ( 2 k + 2 ) x k . This implies that the number of ways to distribute the candy is just ( 2 1 0 0 ) = 4 9 5 0 .
Notice how ( 2 1 0 0 ) is the number of ways to sort 1 0 1 identical candies into three non-empty piles. I'll leave it up to the reader to find a one to one correspondence. :)