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

    HallsofIvy

    User Avatar
    Staff Emeritus
    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!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Enumerative Combinatorics help
Loading...