Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University 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
|
|
|
|
