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

$ x_1 + x_2 + x_3 + x_4 = n $


$ 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 $


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


$\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.

  • $\begingroup$ 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. $\endgroup$ – Mike Jun 15 '15 at 19:41
  • $\begingroup$ Just do a search for "number of compositions". Here is the first hit: en.wikipedia.org/wiki/Composition_(combinatorics) $\endgroup$ – 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.