Enumerative Combinatorics help

[I<3Gauss]

I was reading Stanley's first volume on Enumerative Combinatorics, and I am seemingly stuck on a basic question regarding compositions. It may be that my algebra skills are rusty, but I just cannot get the correct formula for the number of compositions of n into even numbers of even valued parts.

To elaborate, the generating function for the number of compositions of n into k parts where each part is even is
( x^2 + x^4 + x^6 + x^8 ...)^k

After we simplify this equation and look at the coefficients of the expanded polynomial, we should be able to get the formula to answer the above question. I have checked many times, but the incorrect answer that I always come up with is (n-k-1 choose n-2k). I was wondering if someone else can try and derive the formula so that I can see what went wrong with my answer?

 

[HallsofIvy]

It would be better to show your derivation so we can point out any errors.

 

[I<3Gauss]

Okay, here goes

(x^2 + x^4 + x^6 + ...)^k

= (x^2k) (1 + x + x^2 + x^3 + ...)^k

= (x^2k) [(1-x)^-k]

By the general binomial theorem, we now have

= (x^2k) [sum(n=o to infinity) (-k choose n) (-x)^n]

well, we know that (-k choose n) is equal to (-1)^n (k+n-1 choose n)

plugging in, we get

= ((x^2k) [sum(n=0 to infinity) (k+n-1 choose n) x^n]

= [sum(n=0 to infinity) (k+n-1 choose n) x^(n+2k)]

= [sum(n=2k to infinity) (n-k-1 choose n-2k) x^n]

Thus, the compositions of n into even number of even parts should be (n-k-1 choose n-2k).

Note: each part is strictly greater than 0

However, this cannot be right since plugging in say n=6 and k=2 means that there are (3 choose 2) ways, or 3 ways for the composition of 6. However, the composition of 6 into 2 parts where each part is even is only 2+4, and 4+2. Thus, fail.

I am confident, however, that the initial generating function I provided is correct.

 

[JSuarez]

What happened to the (-1)^n factor?

 

[awkward]

Okay, here goes

(x^2 + x^4 + x^6 + ...)^k

= (x^2k) (1 + x + x^2 + x^3 + ...)^k

= (x^2k) [(1-x)^-k]

By the general binomial theorem, we now have

= (x^2k) [sum(n=o to infinity) (-k choose n) (-x)^n]

well, we know that (-k choose n) is equal to (-1)^n (k+n-1 choose n)

plugging in, we get

= ((x^2k) [sum(n=0 to infinity) (k+n-1 choose n) x^n]

= [sum(n=0 to infinity) (k+n-1 choose n) x^(n+2k)]

= [sum(n=2k to infinity) (n-k-1 choose n-2k) x^n]

Thus, the compositions of n into even number of even parts should be (n-k-1 choose n-2k).

Note: each part is strictly greater than 0

However, this cannot be right since plugging in say n=6 and k=2 means that there are (3 choose 2) ways, or 3 ways for the composition of 6. However, the composition of 6 into 2 parts where each part is even is only 2+4, and 4+2. Thus, fail.

I am confident, however, that the initial generating function I provided is correct.

In your first step,

[tex](x^2 + x^4 + x^6 + \dots)^k = x^{2k} (1 + x^2 + x^4 + \dots)^k[/tex]

 

[I<3Gauss]

oh whoops, i c

omg, can't factor...

(x^2 + x^4 + x^6 + x^8)^k

= [ (x^2) (1 + x^2 + x^3 + x^4 +...) ]^k

but 1 + x^2 + x^3 + x^4 + ... does not equal 1/(1-x)

cuz 1/(1-x) = 1 + x + x^2 + x^3 + x^4

Thanks guys, I now know i can do enumerative combinatorics but can't do algebra or factoring...

 

[awkward]

oh whoops, i c

omg, can't factor...

(x^2 + x^4 + x^6 + x^8)^k

= [ (x^2) (1 + x^2 + x^3 + x^4 +...) ]^k

[snip]

Better look closely at that equation.

 

[I<3Gauss]

oh whoops again, typo, thanks for that correction!