Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



(Finite) Generating Functions
Posted:
Dec 3, 2004 12:21 AM


Surely there must be a nice way to solve this problem. I will post the problem and my feeble method of solution.
Write an ordinary generating function for the number of ways of distributing n pieces of candy to 10 kids if the two youngest kids get between 1 and 5 pieces each and each of the other 8 children gets either 1 or two pieces. Use this generating function to find the number of ways to distribute 15 candies.
ogf for youngest: (x + x^2 + ... + x^5) [1] ogf for others: (x + x^2) [2]
Since two youngest square [1] and since eight others, raise [2] to the 8th power. Thus, the ogf is:
(x + x^2 + x^3 + x^4 + x^5)^2 * (x + x^2)^8
Using Maple, I get 520 x^15 so there are 520 ways to do this. My attempt without Maple, and where things get ugly...
(x + x^2 + x^3 + x^4 + x^5)^2 * (x + x^2)^8 = x^2 * (1 + x^2 + x^3 + x^4)^2 * x^8 * (1 + x)^8 = x^10 * (1 + x^2 + x^3 + x^4)^2 * (1 + x)^8 [3]
(1  x^5)^2 (1  x^2)^8 = x^10 *  *  (1  x)^2 (1  x)^8
= x^10 * (1  x)^10 * (1  x^5)^2 * (1  x^2)^8
Now use logic. Since there is an x^10 in front, ignore it momentarily and find the coefficient of x^5 in the other three terms.
The second term can only contribute for powers of x = {0, 5, 10}. However, 10 is not valid since we only need x^5.
The third term can only contribute even powers of x = {0, 2, 4, ..., 16}. The only 'valid' powers are {0, 2, 4}.
The first term can contribute powers of {0, 1, 2, ..., 10}. But using the knowledge of the what the other terms can contribute, we end up with only 4 valid combinations (0, 5, 0) (1, 0, 4) (3, 0, 2) (5, 0, 0) Now find out the coefficients for each of the valid combinations. (0, 5, 0) => 1 for x^0 from the first term => 2 for x^5 from the second => 1 for the x^0 from the last term => 1 * 2 * 1 = 2 (1, 0, 4) => C(10,1) = 10 from the first => 1 from the second => C(8,2) = 28 from the third => 10 * 1 * 28 = 280 (3, 0, 2) => C(12,3) = 220 from the first => 1 from the second => C(8,1) = 8 from the third => 220 * 1 * 8 = 1760 (5, 0, 0) => C(14,5) = 2002 from the first => 1 from the second => 1 from the third => 2002 * 1 * 1 = 2002
Thus there are 2 + 280  1760 + 2002 = 520 ways.
Surely there is an easier way to do this, other than the Maple way. I thought about using [3] above, but I don't think it makes it any easier.
 Tim
 Timothy M. Brauch NSF Fellow Department of Mathematics University of Louisville
email is: news (dot) post (at) tbrauch (dot) com



