Generating functions for finding the coefficients

Question

I am new to the field of combinatorics and I recently came across a problem where it was asked to find the number of integer solutions to ${c_1 + c_2 + c_3 + c_4=20 }$ where ${c_i\ge 0}$ for all ${1\le i\le4}$ with ${c_2}$ and ${c_3}$ being even integers.

Using the generating function, we know that the solution would be the coefficient of ${x^{20}}$ in the expansion of ${(1 +x+x^2+x^3+...)^2*(1+x^2+x^4+x^6+...)^2}$ which is equivalent to: ${(1-x)^{-2}*(1-x^2)^{-2}}$

Now, we know that the first part could be solved by computing:${(-1)^{20}\dbinom{-2}{20} = \dbinom{2+20-1}{20}=21}$

Since we know that: ${(1+x^m)^n = \dbinom{n}{0} + \dbinom{n}{1}x^m + \dbinom{n}{2}x^{2m}+...+\dbinom{n}{n}x^{nm}}$

Would it be correct to assume that the coefficient of ${x^{20}}$ in ${{(1-x^2)^{-2}}}$ would be: ${\dbinom{-2}{10}}$

Answer 1

Yes, the coefficient of $x^{20}$ in $(1-x^2)^{-2}$ is the coefficient of $y^{10}$ in $(1-y)^{-2}$ which is $(-1)^{10}\binom{-2}{10}=\binom{-2}{10}$.

As shown in this answer, $$ \binom{-2}{10}=(-1)^{10}\binom{11}{10}=11 $$

---

Computation of the Coefficients $$ \begin{align} (1-x)^{-2}(1-x^2)^{-2} &=\sum_{j=0}^\infty(-1)^j\binom{-2}{j}x^j\sum_{k=0}^\infty(-1)^k\binom{-2}{k}x^{2k}\\ &=\sum_{j=0}^\infty\sum_{k=0}^{\lfloor j/2\rfloor}(-1)^{j-k}\binom{-2}{j-2k}\binom{-2}{k}x^j\\ &=\sum_{j=0}^\infty\sum_{k=0}^{\lfloor j/2\rfloor}\binom{j-2k+1}{j-2k}\binom{k+1}{k}x^j\\ &=\sum_{j=0}^\infty\sum_{k=0}^{\lfloor j/2\rfloor}(j-2k+1)(k+1)x^j\\ &=\sum_{j=0}^\infty\left[(j+1)\binom{\lfloor j/2\rfloor+2}{2}-4\binom{\lfloor j/2\rfloor+2}{3}\right]x^j\\ &=\sum_{j=0}^\infty\frac{j+3}{48}\left[\left(2j^2+12j+13\right)+(-1)^j3\right]x^j \end{align} $$ using the fact that $\lfloor j/2\rfloor=\frac{2j-1+(-1)^j}4$.

Answer 2

This is an answer with a slightly different approach. We use the the coefficient of operator $[x^t]$ to denote the coefficient $a_t$ of $x^t$ in a series $A(x)=\sum_{j=0}^{\infty}a_jx^j$.

We obtain \begin{align*} [x^t]&(1-x^2)^{-2}(1-x)^{-2}\\ &=[x^t]\sum_{k=0}^{\infty}\binom{-2}{k}(-x^2)^k\sum_{j=0}^{\infty}\binom{-2}{j}(-x)^j\tag{1}\\ &=[x^t]\sum_{k=0}^{\infty}\binom{k+1}{k}x^{2k}\sum_{j=0}^{\infty}\binom{j+1}{j}x^j\tag{2}\\ &=[x^t]\sum_{k=0}^{\infty}(k+1)x^{2k}\sum_{j=0}^{\infty}(j+1)x^j\\ &=\sum_{k=0}^{\left\lfloor t/2\right\rfloor}(k+1)[x^{t-2k}]\sum_{j=0}^{\infty}(j+1)x^j\tag{3}\\ &=\sum_{k=0}^{\left\lfloor t/2\right\rfloor}(k+1)(t-2k+1)\tag{4}\\ &=\sum_{k=1}^{\left\lfloor t/2\right\rfloor+1}\left((t+3)k-2k^2\right)\tag{5}\\ &=\frac{1}{6}\left(\left\lfloor t/2\right\rfloor+1\right)\left(\left\lfloor t/2\right\rfloor+2\right) \left(3t-4\left\lfloor t/2\right\rfloor+3\right)\tag{6} \end{align*}

Comment:

• In (1) we use the series expansion of the binomial series

• In (2) we use the identity $\binom{r}{s}=\binom{-r+s-1}{s}(-1)^s$

• In (3) we use the linearity of the coefficient of operator and the identity $[x^t]x^uA(x)=[x^{t-u}]A(x)$. We also set the upper index of the first sum to $\left\lfloor t/2\right\rfloor$, since the exponent of $x^{t-2k}$ has to be non-negative.

• In (4) we set $j=t-2k$ in order to select the proper coefficient of $x^{t-2k}$.

• In (5) we shift the index by one for simplification only and rearrange the summands according to increasing powers of $k$.

• In (6) we use the summation formula $\sum_{k=1}^{n}k=\frac{n(n+1)}{2}$ and $\sum_{k=1}^{n}k^2=\frac{n(n+1)(2n+1)}{6}$.

Since we need the coefficient of $x^{20}$ we obtain from (6)

\begin{align*} [x^{20}](1-x^2)^{-2}(1-x)^{-2}=\frac{1}{6}\cdot11\cdot12\cdot23=405 \end{align*}

Note, that we do not multiply the series representation of $(1-x^2)^{-2}$ and $(1-x)^{-2}$ using Cauchy multiplication. We walk instead with the coefficient of operator through the series.