Generating functions in discrete mathematics - How to find coefficient from polynomial with multiplication

Question

So I encountered a certain problem when studying generating functions that I seem to be unable to fully solve.

The problem is as follows:

Carol is collecting money from her cousins to have a party for her aunt. If eight of the cousins promise to give 2, 3, 4, or 5 dollars each, and two others each give 5 or 10 dollars, what is the total number of ways Carol can collect exactly 40 dollars?

The solution is the coefficient of the $x^{40}$ term in the generating function

$(x^2 + x^3 + x^4 + x^5)^8(x^5+x^{10})^2$

which may be simplified to finding the coefficient of the $x^{14}$ term in

$(1+x+x^2+x^3)^8(1+x^5) = (\frac{1-x^4}{1-x})^8(1+2x^5+x^{10}) = (1-x^4)^8(1-x)^{-8}(1+2x^5+x^{10})$

This is where I am stuck. To find the coefficient I know that I am suppose to find all possible combinations of how $x^{14}$ can be created by evaluating the polynomial. This would be done quite easily if only the first term $(1-x^4)^8(1-x)^{-8}$ would exist but how I am suppose to do this with the additional term $(1+2x^5+x^{10})$ present? I.e how do I evaluate the different combinations $x^{14}$ may be created and the find the coefficient with the second term present?

There is a solution given in the book, but I do not understand the principle behind it.

Answer 1

We have $1+2x^5+x^{10}$ and also two other complicated factors:

$$(1-x)^{-8}\quad=\quad1+{-8 \choose 1}(-x)+{-8 \choose 2}(-x)^2+\dots+{-8 \choose 4}(-x)^4+{-8 \choose 5}(-x)^5+{-8 \choose 6}(-x)^6+\dots+{-8 \choose 9}(-x)^{9}+{-8 \choose 10}(-x)^{10}+\dots{-8 \choose 14}(-x)^{14}+\dots,$$

$$(1-x^4)^8\quad=\quad1-{8 \choose 1}x^4+{8 \choose 2}x^8-{8 \choose 3}x^{12}+\dots.$$

For $(1-x)^{-8}$, I have shown only the nine factors that are usable for our purpose. For each of these nine, in order:

0. take $x^{10}$ from the first factor; take the $x^4$ term from the third factor.

1. take $2x^{5}$ from the first factor; take the $x^8$ term from the third factor.

2. take $1$ from the first factor; take the $x^{12}$ term from the third factor.

3. take $x^{10}$ from the first factor; take the $1$ term from the third factor.

4. take $2x^{5}$ from the first factor; take the $x^4$ term from the third factor.

5. take $1$ from the first factor; take the $x^8$ term from the third factor.

6. take $2x^{5}$ from the first factor; take the $1$ term from the third factor.

7. take $1$ from the first factor; take the $x^4$ term from the third factor.

8. take $1$ from the first factor; take the $1$ term from the third factor.

Answer 2

It is convenient to use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ in a series. With $A(x)$ a generating function we can write for instance \begin{align*} [x^{14}]\left(1+2x^5+x^{10}\right)A(x)=\left([x^{14}]+2[x^9]+[x^{4}]\right)A(x)\tag{1} \end{align*} In (1) we apply the rule $[x^{p-q}]A(x)=[x^p]x^qA(x)$. In the current situation we obtain \begin{align*} \color{blue}{[x^{14}]}&\color{blue}{\left(1+2x^5+x^{10}\right)\left(1-x^4\right)^8(1-x)^{-8}}\\ &=\left([x^{14}]+2[x^9]+[x^{4}]\right)\left(1-x^4\right)^8(1-x)^{-8}\tag{2}\\ &=[x^{14}]\left(1-\binom{8}{1}x^4+\binom{8}{2}x^8-\binom{8}{3}x^{12}\right)(1-x)^{-8}\\ &\qquad+2[x^{9}]\left(1-\binom{8}{1}x^4+\binom{8}{2}x^8\right)(1-x)^{-8}\\ &\qquad+[x^4]\left(1-\binom{8}{1}x^4\right)(1-x)^{-8}\tag{3}\\ &=\left([x^{14}]-\binom{8}{1}[x^{10}]+\binom{8}{2}[x^6]-\binom{8}{3}[x^{2}]\right)(1-x)^{-8}\\ &\qquad+\left(2[x^9]-2\binom{8}{1}[x^5]+2\binom{8}{2}[x^1]\right)(1-x)^{-8}\\ &\qquad+\left([x^4]-\binom{8}{1}[x^0]\right)(1-x)^{-8}\tag{4}\\ &\,\,\color{blue}{=\binom{-8}{14}(-1)^{14}-\binom{8}{1}\binom{-8}{10}(-1)^{10}}\\ &\qquad\qquad\color{blue}{+\binom{8}{2}\binom{-8}{6}(-1)^6-\binom{8}{3}\binom{-8}{2}(-1)^2}\\ &\qquad\color{blue}{+2\binom{-8}{9}(-1)^9-2\binom{8}{1}\binom{-8}{5}(-1)^5}\\ &\qquad\qquad\color{blue}{+\binom{8}{2}\binom{-8}{1}(-1)^1}\\ &\qquad\color{blue}{+\binom{-8}{4}(-1)^4-\binom{8}{1}\binom{-8}{0}(-1)^0}\tag{5}\\ &=\cdots \end{align*}

Comment:

• In (2) we use the rule we already applied in (1).

• In (3) we expand $\left(1-x^4\right)^8$ up to terms which give a contribution when calculating the coefficient of operator. If for instance $[x^q]$ is given, it is sufficient to expand $\left(1-x^4\right)^8$ up to terms with powers of $x$ less or equal to $q$.

• In (4) we use again the rule $[x^{p-q}]A(x)=[x^p]x^qA(x)$ and the linearity of the coefficient of operator.

• In (5) we select the coefficient of $(1-x)^{-8}$ accordingly.