Please help to find the formula for a relation

Question

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.

Answer 1

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.

Answer 2

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.