Combinatorics: Find the Coefficient of x^36 in this Generatin Function

[Shoney45]

Homework Statement

Find the coefficient of x^36 in (x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8)^6

Homework Equations

1/(1-x) = 1 + x + x^2 +... (where +... indicates an infinite series).

(1 - x^(m+1)/(1-x)) = 1+x+x^2+...+x^m (I'll call this identity 'TWEAK')

The Attempt at a Solution

To get my equation to look like something in the 'relevant equations' I factor an x^2 out of (x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8)^6 to get [x^12(1 + x + x^2 + x^3 + x^4 + x^5 + x^6)^6]. So now I can substitute TWEAK for my polynomial such that [x^12(1 + x + x^2 + x^3 + x^4 + x^5 + x^6)^6] = x^12(1 - x^7)/(1-x).

From here though, I just can't figure out from my book how to proceed.

 

[lanedance]

so it becomes find coeffiecient of x^34 in
(1 + x + x^2 + x^3 + x^4 + x^5 + x^6)^6

so i think you have to pick 6 numbers from 6 numbers with replacement (0,1,2,3,4,5,6), such that they add up to 34

 

[uart]

so it becomes find coeffiecient of x^34 in
(1 + x + x^2 + x^3 + x^4 + x^5 + x^6)^6

so i think you have to pick 6 numbers from 6 numbers with replacement (0,1,2,3,4,5,6), such that they add up to 34

Actually it's x^24 if you factor out the (x^2)^6 like that lanedance. :)

 

[lanedance]

good point, unfortunately that makes it a little harder as there are more combination that add up to 24
666600
666510
666420
666411
666330
666321
666222
...

 

[lanedance]

and so on, not sure if there is a smart way to count those, or an equivalent maybe a generalisation of the binomial theorem

 

[Avodyne]

Your original method will work, though you seem to have some misplaced parentheses.

Start with 1+x+...+x^6 = (1-x^7)/(1-x). Then use

(1-x^7)^6 = 1 - 6x^7 + ...

(1-x)^(-6) = 1 + 6x + ...

Compute each of these series out to x^24. There are only a few terms in the first one, and there is a simple formula for the coefficients of the second one.

Then, take their product, and figure out which terms contribute to the coefficient of x^24.