Finding Coefficient of x^n in 1/((1-x)(1-x^2)(1-x^3)) - Generating Functions

[adil]

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?

 

[mathman]

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.

 

[adil]

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.

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?

 

[LittleWolf]

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.

 

[matt grime]

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?

If it works for every "fixed n" then surely that is a "general" result?

 

[TenaliRaman]

If it works for every "fixed n" then surely that is a "general" result?

**Chuckle**
I think he is asking, whether there is a closed form for that.

-- AI

 

[BicycleTree]

Here is a clumsy summation for it (E for summation over):
E(i = 1 to floor(n / 3)) (floor((n-(3 * i)) / 2) + 1)

 

[BicycleTree]

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.

 

[LittleWolf]

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.

 

[BicycleTree]

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.