Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Generating functions

  1. Jun 6, 2005 #1
    Does anybody know how to find the coefficient of x^n in 1/((1-x)(1-x^2)(1-x^3))? I've simplified the above to (1+x+x+x^2+....)(1+x^2+x^4+...)(1+x^3+x^6+...), but don't know where to go from here. Any ideas?
  2. jcsd
  3. Jun 6, 2005 #2


    User Avatar
    Science Advisor

    Let n=j+2k+3m, where j,k,m are non-negative integers. Count how many different combinations of (j,k,m) you can get. That's your answer.
  4. Jun 6, 2005 #3
    Thanks, but doesn't this method only work for fixed n?... let n=2, then I can get x^2 from x^2.1.1 or 1.x^2.1, so the coefficient would be 2. The method doesn't work for general n does it?
  5. Jun 9, 2005 #4
    I took your problem and used Mathematica to do a partial fraction decomposition:
    1/((1-x)(1-x^2)(1-x^3))=1/(6*(1-x)^3)+1/(4(1-x)^2)+17/(72(1-x))+1/(8(1+x))+(2+x)/(9(1+x+x^2)). I think you should be able to determine the nth term for each fraction when you expand them out as a series.
  6. Jun 10, 2005 #5

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    If it works for every "fixed n" then surely that is a "general" result?
  7. Jun 11, 2005 #6
    I think he is asking, whether there is a closed form for that. :smile:

    -- AI
  8. Jun 11, 2005 #7
    Here is a clumsy summation for it (E for summation over):
    E(i = 1 to floor(n / 3)) (floor((n-(3 * i)) / 2) + 1)
  9. Jun 11, 2005 #8
    Here's the answer for when 2 and 3 divide n:

    n^2 / 12 + n / 2 + 1

    I got this by drawing pictures and reasoning... no idea how to simplify the summation of my previous post analytically. It checks for n = 6 and n = 12 at least; I have not done n = 18 by hand to check the formula but if someone would like to try that they can.
  10. Jun 11, 2005 #9
    BicycleTree, bravo. I checked your summation and wrote it a little differently:
    Sum(Floor[(n-3i)/2+1), i=0,1,...floor(n/3)]). Using the partial fractions , this also works 17/72+C(n+1,1)/4+C(n+2,2)/6+g(n)/8+h(n)/9 where C(n,k) is n choose k,
    g(n)=1 if 2 divides n otherwise g(n)=-1, and h(n)=2 if 3 divides n otherwise h(n)=-1.
    It would be fun to see how you derived your summation. Again, Good Job. Also,your quadratic equation works for these additional n= 18,24,30,36.
  11. Jun 12, 2005 #10
    I got the summation this way:
    In n=j+2k+3m, write the number n as a bunch of circles from left to right. Consider the entire number "filled up" by 1's, one 1 to a circle. This is 1 possible sum, corresponding to j = n, k = 0, m = 0. Then starting at the left, group 2 circles together. This is another possible sum, corresponding to j = n-2, k = 1, m = 0. Then group another two circles from the left, corresponding to j = n-4, k = 2, m = 0. It can be seen from this that the number of ways to form n using only 1's and 2's is floor(n/2) + 1.

    Then deal with 3's. For each amount of threes you use (say there are i threes) you have n - 3i left to form using only 1's and 2's. And you can have 0, 1, ..., floor(n/3) threes. From this I get the summation.

    Also, if your equation is correct then my quadratic is also correct for all n divisible by 6. How I got the quadratic is interesting. Consider a group of 6 units when n is written out like I said earlier (in unary). This group is either the rightmost group, or there are 6 units between it and the right, or 12, so on up to n-6 units to the right of it. Now say that the entire number to the left of that group has been filled up by 3's, and the left half of the group is also covered by a 3, and that there are no threes to the right of that group. Given that, the question is, how many ways are there to fill the as-yet-unfilled part of the number with 1's, 2's, and 3's? (see attachment)

    So sum up the groups of 6: E(i = 0 to n/6) (6i/2 + 1 + (6i + 2) / 2 + 1). But this is an overcount, because when i = n/6, x = n and y = n + 3 in the diagram. x = n is a case you do want to count, but y = n + 3 is the case when n has been filled from the left by "negative one" threes. So subtract (n + 2) / 2 + 1 back out, for (E(i = 0 to n/6) (6i/2 + 1 + (6i + 2) / 2 + 1)) - ((n + 2) / 2 + 1). This simplifies to n^2 / 12 + n / 2 + 1.

    Attached Files:

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook