# Generating function for counting compositions of $n$ with parts from a given set

I was given the next question:

$A_n$ is marked to be the number of all of the sequences from a subset of the naturals to $\{1,2,3,4,5,6\}$ such that their sum is $n$ (a natural number) ** which means that the order matters

For example: for $A_5$ some part of the sequences are <1,1,1,1,1> , <1,2,2> , <2,2,1>

I was asked to find the generating function that suits this problem, and what I mean by this is finding the function $f$ such that $f$= $A_0$ + $A_1x$ + $A_2x^2$+...

I'd really like some help with this question, Thank you very much!

p.s.: $A_0=0$

• Did you try to find the possible recursive relation of $A_n$'s? – Στέλιος Σαχπάζης Jan 14 '17 at 9:05
• @SachpazisStelios Sadly I cannot use recursive methods because we did not study those yet =( – Lola Jan 14 '17 at 9:11
• I was asked to prove it using generating functions..how will induction be helpful in this case? @charMD – Lola Jan 16 '17 at 22:59

## 1 Answer

We observe: $$\frac{x}{1-x}=x^1+x^2+x^3+\ldots$$ carries as exponents the possible solutions $1,2,3,\ldots$ of one $x_i$ in $$x_1+x_2+x_3+\ldots+x_k=n\qquad k\geq 1, n\geq k$$ Therefore the number of compositions of $n$ with $k$ variables $x_1,x_2,\ldots,x_k$ is the coefficient of $x^n$ of $$\left(\frac{x}{1-x}\right)^k$$

Since we want to restrict the solutions to be elements from $\{1,2,3,4,5,6\}$ we take \begin{align*} \frac{x-x^7}{1-x}=x^1+x^2+x^3+x^4+x^5+x^6 \end{align*}

Since the number of variables is at least $1$ up to $n$ for $A_n$ we obtain as generating function \begin{align*} f(x)&=\sum_{n=1}^\infty A_nx^n\\ &=\sum_{n=1}^\infty \left(\frac{x-x^7}{1-x}\right)^n\\ &=\frac{x-x^7}{1-x}\cdot\frac{1}{1-\frac{x-x^7}{1-x}}\\ &=x+2x^2+4x^3+8x^4+\color{blue}{16}x^5+32x^6+63x^7+\cdots \end{align*}

whereby the last line was obtained with some help of Wolfram Alpha.



Example: We find e.g. $A_5=16$ which represents the $\color{blue}{16}$ compositions of $5$ \begin{align*} &<1,1,1,1,1,1>,\\ &<1,1,1,2>,<1,1,2,1>,<1,2,1,1>,<2,1,1,1>,\\ &<1,1,3>,<1,3,1>,<3,1,1>\\ &<1,2,2>,<2,1,2>,<2,2,1>\\ &<1,4>,<4,1>\\ &<2,3>,<3,2>\\ &<5> \end{align*}

• @Lola: You're welcome! :-) – Markus Scheuer Jan 16 '17 at 23:17
• @Lola: Thanks a lot for granting the bounty! :-) – Markus Scheuer Jan 17 '17 at 13:09
• No problem :) Sorry for the bother Markus Scheuer, but could you help me with my recent question in generating functions? The answer that was given there was a false one =( – Lola Jan 18 '17 at 7:33
• @Lola: I've added an answer. Regards, – Markus Scheuer Jan 18 '17 at 17:13