<s>[INST] Generating functions in discrete mathematics - How to find coefficient from polynomial with multiplication 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.

 [/INST] 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.
</s>