Find coefficient of ordinary generating function

Question

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)?

Answer 1

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.