# Enumerative Combinatorics help

1. Sep 4, 2010

### 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?

2. Sep 4, 2010

### HallsofIvy

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

3. Sep 4, 2010

### 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.

4. Sep 4, 2010

### JSuarez

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

5. Sep 4, 2010

### awkward

$$(x^2 + x^4 + x^6 + \dots)^k = x^{2k} (1 + x^2 + x^4 + \dots)^k$$

6. Sep 4, 2010

### I<3Gauss

oh whoops, i c

omg, cant 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 cant do algebra or factoring.....

7. Sep 4, 2010

### awkward

Better look closely at that equation.

8. Sep 4, 2010

### I<3Gauss

oh whoops again, typo, thanks for that correction!