Enumerative Combinatorics help

  • Thread starter Thread starter I<3Gauss
  • Start date Start date
  • Tags Tags
    Combinatorics
I<3Gauss
Messages
14
Reaction score
0
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?
 
Mathematics news on Phys.org
It would be better to show your derivation so we can point out any errors.
 
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.
 
What happened to the (-1)^n factor?
 
I<3Gauss said:
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,

(x^2 + x^4 + x^6 + \dots)^k = x^{2k} (1 + x^2 + x^4 + \dots)^k
 
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...
 
I<3Gauss said:
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.
 
oh whoops again, typo, thanks for that correction!
 
Back
Top