Problem 15 Generating Functions

Problem 15: Generating Functions

AoPS

Problem: Find the number of non-negative integer solutions to x + 2y + 4z = 50. Solution: The x can give you any integer from 0 onwards, so it has a GF of 1+x+x2 +x3 ... = 1 1−x . The 2y can give you any integer multiple of 2 from 0 onwards, so it has a GF of 1 + x2 + 1 x4 + x6 ... = 1−x 2. The 4z can give you any integer multiple of 4 from 0 onwards, so it has a GF of 1 + x4 + 1 x8 + x12 ... = 1−x 4. We multiply these GFs: 1 1 1 )( )( ) 2 1 − x 1 − x 1 − x4 Now we want to make the exponents of this GF easier to evaluate, so we manipulate it a little bit: (

1 1+x (1 + x)(1 + x2 )2 = = (1 − x)(1 − x2 )(1 − x4 ) (1 − x2 )2 (1 − x4 ) (1 − x4 )3 We can use binomial theorem on the denominator, and we see we can multiply out the numerator to make things simpler. We do so and get: x5 + x4 + 2x3 + 2x2 + x + 1 = (x5 + x4 + 2x3 + 2x2 + x + 1)(1 − x4 )−3 (1 − x4 )3 We are looking for the coefficient of x50 , and we realize that every term in (1 − x4 )−3 will be of the form 1, x4 , x8 , x12 .... Thus the only way we can combine terms to get an x50 is to multiply the 2x2 and then some ax48 . So now all we have left to do is find the coefficent of x48 in (1 − x4 )−3 . This is equivalent to the coefficent of x12 in (1 − x)−3   12 + 3 − 1 By binomial theorem, this will be = 91. 12 So we know we have 91x48 . Multiply this with 2x2 and we get 182x50 . So the coefficient of x50 is 182 .

Solution was written by Sean Soni and compiled from Art of Problem Solving Forums.