[Math] Generating Functions – Extracting Coefficients

combinatoricsdiscrete mathematicsgenerating-functionspower series

In many counting problems, we find an appropriate generating function which allows us to extract a given coefficient as our answer.

In cases where the generating function is not one that is easily used as an infinite sum, how does one alter the generating function for simpler coefficient extraction? The question I'm looking at involves the following generating function:

f(x) = ($x^3$ + $x^4$ + . . . + $x^8$)$^4$, and we seek the coefficient of $x^2$$^4$ in f(x). To start, we convert to a simpler form. With ($x^3$ + $x^4$ + . . . + $x^8$)$^4$ = $x^1$$^2$(1 + x + $x^2$ + . . . + $x^5$)$^4$ = $x^1$$^2$((1 – $x^6$)/(1 – x))$^4$, the answer is the coefficient of $x^1$$^2$ in (1 – $x^6$)$^4$(1 – x)$^-$$^4$

Why is this true? How does $x^1$$^2$ come about, allowing for the common (1 + x + $x^2$ + . . . ) sum ?

Best Answer

You are looking for the coefficient of $x^{24}$ in:$$x^{12}\left(\frac{1-x^6}{1-x}\right)^4$$

Which is the same as the coefficient of $x^{24-12}=x^{12}$ in $$\left(\frac{1-x^6}{1-x}\right)^4\tag{1}$$

Now, $$(1-x^6)^4 = 1-4x^6+6x^{12}-4x^{18}-x^{24}$$

And $$\frac{1}{(1-x)^4} = \sum_{n=0}^{\infty} \binom{n+3}{3}x^n$$

So what is the coefficient of $x^{12}$ in the product? It is $$\binom{12+3}{3}\cdot 1 + \binom{6+3}{3}\cdot (-4) + \binom{3}{3}\cdot 6$$

More generally, the coefficient of $x^k$ in (1) is:

$$\binom{k+3}{3}\cdot 1 + \binom{k-3}{3}\cdot (-4) + \binom{k-9}{3}\cdot 6 +\binom{k-15}{3}\cdot (-4) + \binom{k-21}{3} \cdot 1$$

And yes, if $k>20$ this will evaluate as zero.