5
$\begingroup$

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 :-(

Thanks in advance.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Jack D'Aurizio May 11 '15 at 15:25
  • 2
    $\begingroup$ The "money change problem" is a great introduction to analytic combinatorics. $\endgroup$ – Jack D'Aurizio May 11 '15 at 15:26
  • $\begingroup$ 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. $\endgroup$ – Henry May 11 '15 at 15:36
  • $\begingroup$ 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 $\endgroup$ – D1Fu May 11 '15 at 16:05
2
$\begingroup$

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*}

$\endgroup$

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.