Generating Functions to Polynomial

Question

Let $d_n$ be the number of ordered sequences of die rolls (i.e., sequences of integers from $1$ to $6$) that add up to $n$. For example, $d_4=8$, because a total of $4$ can be rolled in $8$ ways:

$$\begin{array}{*4c} 4 & 3+1 & 2+2 & 1+3 \\ \\ ~2+1+1~ & ~1+2+1~ & ~1+1+2~ & ~1+1+1+1~ \end{array}$$ and $d_0=1$, since $0$ can be rolled in one way (roll no dice).

Let $D(x)$ be the generating function $$D(x) = d_0 + d_1x + d_2x^2 + d_3x^3 + \cdots .$$ Then $\frac 1{D(x)}$ is a polynomial. What polynomial is it?

---

Isn't the generating function a polynomial? And I don't know how to start this problem...

Answer 1

Consider $$ \frac{1}{1-(x+x^2+x^3+x^4+x^5+x^6)} $$ Using the power series expansion of $\frac{1}{1-x}$, we find that this is: $$ 1+(x+x^2+x^3+x^4+x^5+x^6)+(x+x^2+x^3+x^4+x^5+x^6)^2+(x+x^2+x^3+x^4+x^5+x^6)^3+\cdots. $$ In this sum, the powers of the $x$'s represent the die rolls. For example,

The $1$ corresponds to $1\cdot x^0$, i.e., there is one way to get a sum of $1$ (don't roll any dice).

The $(x+x^2+x^3+x^4+x^5+x^6)$ represents the $6$ possibilities from a single die roll.

The $(x+x^2+x^3+x^4+x^5+x^6)^2$ represents the $36$ possibilities for two die rolls.

For example, if you roll a $3$ first and then a $2$, this corresponds to the terms of product $$(x+x^2+\color{red}{x^3}+x^4+x^5+x^6)(x+\color{red}{x^2}+x^3+x^4+x^5+x^6).$$ In general, the coefficient of $x^n$ is the number of ordered ways to get a value of $n$. Therefore, $$ D(x)=\frac{1}{1-(x+x^2+x^3+x^4+x^5+x^6)}. $$ More specifically, notice that the number of ways to get a sum of $3$ is $4$: $(1,1,1)$, $(1,2)$, $(2,1)$, $(3)$. Note that in the expansion of $D(x)$, the ways to get $x^3$ are

$x^1\cdot x^1\cdot x^1$ in $(x+x^2+x^3+x^4+x^5+x^6)^3$

$x^1\cdot x^2$ in $(x+x^2+x^3+x^4+x^5+x^6)^2$

$x^2\cdot x^1$ in $(x+x^2+x^3+x^4+x^5+x^6)^2$ and

$x^3$ in $(x+x^2+x^3+x^4+x^5+x^6)$

which correspond to the ways to get sum of $3$, as listed above.