Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: (Finite) Generating Functions
Replies: 0

 Tim Brauch Posts: 201 Registered: 12/6/04
(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) =&gt; 1 for x^0 from the first term
=&gt; -2 for x^5 from the second
=&gt; 1 for the x^0 from the last term
=&gt; 1 * -2 * 1 = -2
(1, 0, 4) =&gt; C(10,1) = 10 from the first
=&gt; 1 from the second
=&gt; C(8,2) = 28 from the third
=&gt; 10 * 1 * 28 = 280
(3, 0, 2) =&gt; C(12,3) = 220 from the first
=&gt; 1 from the second
=&gt; -C(8,1) = -8 from the third
=&gt; 220 * 1 * -8 = -1760
(5, 0, 0) =&gt; C(14,5) = 2002 from the first
=&gt; 1 from the second
=&gt; 1 from the third
=&gt; 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