1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Enumerative Combinatorics help

  1. Sep 4, 2010 #1
    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. jcsd
  3. Sep 4, 2010 #2


    User Avatar
    Science Advisor

    It would be better to show your derivation so we can point out any errors.
  4. Sep 4, 2010 #3
    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.
  5. Sep 4, 2010 #4
    What happened to the (-1)^n factor?
  6. Sep 4, 2010 #5
    In your first step,

    [tex](x^2 + x^4 + x^6 + \dots)^k = x^{2k} (1 + x^2 + x^4 + \dots)^k[/tex]
  7. Sep 4, 2010 #6
    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.....
  8. Sep 4, 2010 #7
    Better look closely at that equation.
  9. Sep 4, 2010 #8
    oh whoops again, typo, thanks for that correction!
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook