# Coefficients of (generating) function

If I have the generating function \begin{equation*} A(x)= \frac{1}{(1-x^{10})\cdot(1-x^5)\cdot(1-x) }\,, \end{equation*} what is a clean way to find the coefficients of $x^{n}$. This coefficient would tell me, in how many ways I can combine an element of the first, the second and the third to get $x^n$. I am pretty new to generating functions and I only now how to set them up from a series, but not how to get the series from a function :-(

• You have to use partial fraction decomposition. Locate the roots of the denominator and try to write $A(x)$ as a sum of terms like $\frac{1}{x-\xi},\frac{1}{(x-\xi)^2}$ or $\frac{1}{(x-\xi)^3}$, then exploit the well-known Taylor series of such "smaller" terms. – Jack D'Aurizio May 11 '15 at 15:25
• The "money change problem" is a great introduction to analytic combinatorics. – Jack D'Aurizio May 11 '15 at 15:26
• Apart from being a pennies, nickels and dimes change problem as in OEIS A187243, it is also related to quarter-squares OEIS A002620, so one possible formula is $\Bigg\lfloor\dfrac{\Big\lfloor \frac{n+10}{5}\Big\rfloor^2}{4}\Bigg\rfloor$ though perhaps this does not count as clean. – Henry May 11 '15 at 15:36
• The comment about the money change problem helped me finding a recursive way of defining the problem. But I am still curious about the generating function, since this is such a nice way to look at problems. I have problems with the last part about the taylor series. Could you give me an example or explain it again. Sorry for the inconvenience – D1Fu May 11 '15 at 16:05

We can apply the geometric series expansion to derive the coefficients of \begin{align*} A(x)&=\frac{1}{\left(1-x^{10}\right)\left(1-x^5\right)\left(1-x\right)}\\ &=1 + x + x^2 + x^3 + x^4 + 2 x^5 + 2 x^6 + 2 x^7 + 2 x^8 + 2 x^9\\ &\qquad + 4 x^{10} + \cdots+ 4 x^{14} + 6 x^{15} + \cdots + 6 x^{19}\\ &\qquad + 9 x^{20} + \cdots + 9 x^{24} + 12 x^{25} + \cdots + 12 x^{29}\\ &\qquad + 16 x^{30} + \cdots + 16 x^{34} + 20 x^{35} + \cdots + 20 x^{39}\\ &\qquad + 25 x^{40} + \cdots + 25 x^{44} + 30 x^{45} + \cdots + 30 x^{49}\\ &\qquad + \cdots \end{align*}

We start with \begin{align*} \color{blue}{A(x)}&\color{blue}{=\frac{1}{\left(1-x^{10}\right)\left(1-x^5\right)\left(1-x\right)}}\\ &=\frac{1}{1-x}\left(\sum_{j=0}^\infty x^{10j}\right)\left(\sum_{k=0}^\infty x^{5k}\right)\\ &=\frac{1}{1-x}\left(\sum_{n=0}^\infty\left(\sum_{{10j+5k=n}\atop{j,k\geq 0}}1\right)x^n\right)\tag{1}\\ &=\frac{1}{1-x}\left(\sum_{n=0}^\infty\left(\sum_{{2j+k=n}\atop{j,k\geq 0}}1\right)x^{5n}\right)\tag{2}\\ &=\frac{1}{1-x}\left(\sum_{n=0}^\infty\left(\sum_{j=0}^{\lfloor{n/2}\rfloor}1\right)x^{5n}\right)\tag{3}\\ &=\left(\sum_{m=0}^\infty x^m\right)\left(\sum_{n=0}^\infty\left(\left\lfloor\frac{n}{2}\right\rfloor+1\right)x^{5n}\right)\tag{4}\\ &=\sum_{t=0}^\infty\left(\sum_{{m+5n=t}\atop{m,n\geq 0}}\left(\left\lfloor\frac{n}{2}\right\rfloor+1\right)\right)x^t\tag{5}\\ &=\sum_{t=0}^\infty\left(\sum_{n=0}^{\lfloor t/5\rfloor}\left(\left\lfloor\frac{n}{2}\right\rfloor+1\right)\right)x^t\tag{6}\\ \end{align*} and denoting with $$[x^t]$$ the coefficient of $$x^t$$ in a series we observe from (6) \begin{align*} \color{blue}{[x^t]A(x)=\sum_{n=0}^{\lfloor t/5\rfloor}\left\lfloor\frac{n}{2}\right\rfloor+\left\lfloor\frac{t}{5}\right\rfloor+1}\tag{7} \end{align*} which is already a nice formula for the coefficients of $$A(x)$$.

Comment:

• In (1) we apply the Cauchy-multiplication of series.

• In (2) we note that only multiples of $$5n$$ of the index $$n$$ do contribute.

• In (3) we rewrite the sum by eliminating the index $$k$$ and using the floor function $$x\leq \lfloor x\rfloor < x+1$$.

• In (4) we evaluate the inner sum and expand the factor $$\frac{1}{1-x}$$.

• In (5) we do again a Cauchy-multiplication.

• In (6) we eliminate the index $$m$$ from the inner sum.

If we like we can derive a closed formula from (7) by noting that \begin{align*} \color{blue}{\sum_{n=0}^N\left\lfloor\frac{n}{2}\right\rfloor} &=\sum_{{n=0}\atop{ n\equiv 0(2)}}^N\frac{n}{2}+\sum_{{n=0}\atop{ n\equiv 1(2)}}^N\frac{n-1}{2}\\ &=\sum_{n=0}^N\frac{n}{2}\left(\frac{1+(-1)^n}{2}\right)+\sum_{n=0}^N\frac{n-1}{2}\left(\frac{1-(-1)^n}{2}\right)\\ &=\frac{1}{2}\sum_{n=0}^N n-\frac{1}{2}\sum_{n=0}^N\left(\frac{1-(-1)^n}{2}\right)\\ &\,\,\color{blue}{=\frac{1}{4}N(N+1)-\frac{1}{2}\left\lfloor\frac{N+1}{2}\right\rfloor} \tag{8} \end{align*} We finally obtain from (7) and (8) by setting $$N=\lfloor t/5\rfloor$$: \begin{align*} \color{blue}{[x^t]A(x)}&=\sum_{n=0}^{\lfloor t/5\rfloor}\left\lfloor\frac{n}{2}\right\rfloor+\left\lfloor\frac{t}{5}\right\rfloor+1\\ &=\frac{1}{4}\left\lfloor\frac{t}{5}\right\rfloor\left(\left\lfloor\frac{t}{5}\right\rfloor+1\right)-\frac{1}{2}\left\lfloor\frac{\left\lfloor\frac{t}{5}\right\rfloor+1}{2}\right\rfloor+\left\lfloor\frac{t}{5}\right\rfloor+1\\ &\,\,\color{blue}{=\frac{1}{4}\left\lfloor\frac{t}{5}\right\rfloor^2+\frac{5}{4}\left\lfloor\frac{t}{5}\right\rfloor -\frac{1}{2}\left\lfloor\frac{t}{10}+\frac{1}{2}\right\rfloor+1} \end{align*}