Find coefficient of ordinary generating function I'm having a hard time understanding how to find the coefficient of a generating function. I'm working through the example from my book (as shown in the photo). I see the answer is C(18, 15) - C(4,1)*C(12,9) + C(4,2)*C(6,3) and I understand why we care about the coefficient of C(18,15)  or (x^15) but why do we want to subtract and add the coefficients from these other terms specifically? Why wouldn't the answer just be C(18,15)?


In the following we use $\binom{n}{k}:=C(n,k)$ to denote the binomial coefficient $n$ choose $k$. It is convenient to use the coefficient of operator $[x^k]$ to denote the coefficient of $x^k$ in a series. This way we can write e.g.
\begin{align*}
[x^k](1+x)^n=\binom{n}{k}
\end{align*}

We obtain
  \begin{align*}
[x^{27}]&\left(x^3+x^4+\cdots+x^8\right)^{4}\\
&=[x^{27}]x^{12}\left(1+x+\cdots+x^5\right)^{4}\tag{1}\\
&=[x^{15}]\left(1+x+\cdots+x^5\right)^{4}\tag{2}\\
&=[x^{15}]\left(1-x^6\right)^4\left(1+x+x^2+\cdots\right)^4\tag{3}\\
&=[x^{15}]\left(1-\binom{4}{1}x^6+\binom{4}{2}x^{12}-\binom{4}{3}x^{18}+\binom{4}{4}x^{24}\right)\\
&\qquad\qquad\cdot
\left(1+\binom{4}{1}x+\binom{5}{2}x^2+\binom{6}{3}x^3+\cdots\right)\tag{4}\\
&=[x^{15}]\left(1-\binom{4}{1}x^6+\binom{4}{2}x^{12}\right)\cdot
\left(1+\binom{4}{1}x+\binom{5}{2}x^2+\binom{6}{3}x^3+\cdots\right)\tag{5}\\
&=\left([x^{15}]-\binom{4}{1}[x^9]+\binom{4}{2}[x^3]\right)\cdot
\left(1+\binom{4}{1}x+\binom{5}{2}x^2+\binom{6}{3}x^3+\cdots\right)\tag{6}\\
&=\binom{18}{15}-\binom{4}{1}\binom{12}{9}+\binom{4}{2}\binom{6}{3}\tag{7}\\
&=816-4\cdot220+6\cdot20\\
&=56
\end{align*}
  and the claim follows.

Comment:


*

*In (1) we factor out $x^3$ and since we have to take the forth power we get $x^{12}$.

*In (2) we use the rule
\begin{align*}
[x^p]x^qA(x)=[x^{p-q}]A(x)
\end{align*}

*In (3) we apply Theorem 2.2.1 of the book. This theorem effectively uses the summation formula for a finite geometric series
\begin{align*}
1+x+x^2+\cdots+x^n=\frac{1-x^{n+1}}{1-x}
\end{align*}
here with $n=5$ and it also uses the binomial series expansion with $\alpha =-4$ to obtain
\begin{align*}
\frac{1}{(1-x)^4}&=\sum_{n=0}^\infty \binom{-4}{n} (-x)^n\\
&=\sum_{n=0}^\infty \binom{n+3}{n}x^n\\
&=1+\binom{4}{1}x+\binom{5}{2}x^2+\binom{6}{3}x^3+\cdots
\end{align*}
Putting all together we get the right hand side of (3)
\begin{align*}
\left(1+x+\cdots+x^5\right)^{4}&=\left(\frac{1-x^6}{1-x}\right)^4\\
&=\left(1-x^6\right)^4\left(1+\binom{4}{1}x+\binom{5}{2}x^2+\binom{6}{3}x^3+\cdots\right)
\end{align*}

*In (4) we expand both, polynomial and series.

*In (5) we observe that powers $x^{18}$ and $x^{24}$ of the polynomial do not contribute anything to $[x^{15}]$ and can so be safely skipped.

*In (6) we use the linearity of the coefficient of operator and apply again the rule as we did in (2).

*In (7) we select the coefficients of $[x^{15}], [x^9]$ and $[x^3]$ of the series and obtain the representation in the book.
