I'm trying to find the formula for the following relation:

$x_1 + x_2 + x_3 + x_4 = n$

where:

$0 \leq x_1 \leq 3$

$0 \leq x_2 \leq 3$

$x_3 \geq 0$

$x_3 \geq 0$

Let $a_n$ be the number of different compositions of $n$ items.

Here is the generating-function I've made for $\{a_n\}$ sequence according to the limitations:

$(1+x+x^2+x^3)^2\left(\frac{1}{(1-x)^2}\right)$

How to find the formula of $a_n$?

$a_0 = 1$

$a_1 = 4$

Regards.

• Please check the question... the seems to be something missing – b00n heT Jun 15 '15 at 17:54
• Now it's better? – Mike Jun 15 '15 at 17:55
• Well... maybe we have a different understanding of generating function, but to me the one you wrote makes no sense. – b00n heT Jun 15 '15 at 17:56
• Instead of $n$, should the right side be $\sum_{n=0}^{\infty} a_n$? – marty cohen Jun 15 '15 at 18:05
• I've made some editing, hope now it's looking better. Sorry everybody. – Mike Jun 15 '15 at 18:12

I am assuming that the desired relation is $(1+x+x^2+x^3)^2(\frac{1}{(1-x)^2}) =\sum_{n=0}^{\infty} a_n$.

Then

$\begin{array}\\ \sum_{n=0}^{\infty} a_n &=(1+x+x^2+x^3)^2(\frac{1}{(1-x)^2})\\ &=(\frac{1-x^4}{1-x})^2(\frac{1}{(1-x)^2})\\ &=\frac{(1-x^4)^2}{(1-x)^4}\\ &=(1-x^4)^2(1-x)^{-4}\\ &=(1-x^4)^2\sum_{n=0}^{\infty} \binom{-4}{n}(-1)^n x^n\\ &=(1-x^4)^2\sum_{n=0}^{\infty} (-1)^n\binom{n+3}{3}(-1)^n x^n\\ &=(1-2x^4+x^8)\sum_{n=0}^{\infty} \binom{n+3}{3} x^n\\ &=\sum_{n=0}^{\infty} \binom{n+3}{3} x^n -2\sum_{n=0}^{\infty} \binom{n+3}{3} x^{n+4} +\sum_{n=0}^{\infty} \binom{n+3}{3} x^{n+8}\\ &=\sum_{n=0}^{\infty} \binom{n+3}{3} x^n -2\sum_{n=4}^{\infty} \binom{n-1}{3} x^{n} +\sum_{n=8}^{\infty} \binom{n-5}{3} x^{n}\\ &=\sum_{n=0}^{7} \binom{n+3}{3} x^n -2\sum_{n=4}^{7} \binom{n-1}{3} x^{n} +\sum_{n=8}^{\infty} (\binom{n+3}{3}-2\binom{n-1}{3}+\binom{n-5}{3}) x^{n}\\ &=\sum_{n=0}^{3} \binom{n+3}{3} x^n +\sum_{n=4}^{7} (\binom{n+3}{3}-2\binom{n-1}{3}) x^{n} +\sum_{n=8}^{\infty} (\binom{n+3}{3}-2\binom{n-1}{3}+\binom{n-5}{3}) x^{n}\\ \end{array}$

This gives all values of $a_n$. The expressions for $a_n$ for $n \ge 8$ can be simplified, because the $n^3$ and, possibly, the $n^2$ will drop out.

• Thanks! I need an expression for $a_n$ such that when I plug a number in place of $n$ it will produce me be the number of different compositions of $n$ items. – Mike Jun 15 '15 at 19:41
• Just do a search for "number of compositions". Here is the first hit: en.wikipedia.org/wiki/Composition_(combinatorics) – marty cohen Jun 15 '15 at 20:31

Your generating function is correct. Here is the Mathematica code for the Taylor series expansion about x=0 of your g.f.: nn = 20; CoefficientList[Series[((1 - x^4)/(1 - x))^2/(1 - x)^2, {x, 0, nn}], x]. It returns: 1, 4, 10, 20, 33, 48, 64, 80, 96, 112, 128, 144, 160, 176, 192, 208,224, 240, 256, 272, 288,...

You can see the terms are increasing by 16 after n=5 (which makes sense because for n>=6 we have run through the cases dictated by the first two summands).

The formula is (for n>=5), a(n)= 16*n - 32.

• Hi, Can you explain a bit how did you get from the generating function to the formula? I can't track the steps... – Mike Jun 16 '15 at 8:29