Question

Give a combinatorial interpretation of the coefficient of $x^4$ in the expansion ${\left(1+x+x^2+x^3+\cdots \right)}^3$. Use this interpretation to find this number.

Short answer

The combinatorial interpretation of the coefficient of $x^4$ is 15.

Step-by-step solution

Use Permutation and Combination:

Permutation:

No repetition allowed:$\mathit{P}\mathbf{(}\mathit{n}\mathbf{,}\mathit{r}\mathbf{)}\mathbf{=}\frac{\mathbf{n}\mathbf{!}}{\mathbf{(}\mathbf{n}\mathbf{-}\mathbf{r}\mathbf{)}\mathbf{!}}$

Repetition allowed:${\mathbf{n}}^{\mathbf{r}}$

Combination:

No repetition allowed:

$\mathit{C}\mathbf{(}\mathit{n}\mathbf{,}\mathit{r}\mathbf{)}\mathbf{=}\left(\begin{array}{c}n\\ r\end{array}\right)\mathbf{=}\frac{\mathbf{n}\mathbf{!}}{\mathbf{r}\mathbf{!}\mathbf{(}\mathbf{n}\mathbf{-}\mathbf{r}\mathbf{)}\mathbf{!}}$

Repetition allowed: $\mathit{C}\mathbf{(}\mathit{n}\mathbf{+}\mathit{r}\mathbf{-}\mathbf{1}\mathbf{,}\mathit{r}\mathbf{)}\mathbf{=}\frac{\mathbf{(}\mathbf{n}\mathbf{+}\mathbf{r}\mathbf{-}\mathbf{1}\mathbf{)}\mathbf{!}}{\mathbf{r}\mathbf{!}\mathbf{(}\mathbf{n}\mathbf{-}\mathbf{1}\mathbf{)}\mathbf{!}}$with $\mathit{n}\mathbf{!}\mathbf{=}\mathit{n}\mathbf{·}\mathbf{(}\mathit{n}\mathbf{-}\mathbf{1}\mathbf{)}\mathbf{·}\mathbf{\dots }\mathbf{·}\mathbf{2}\mathbf{·}\mathbf{1}$

The expression is given by:

${\left(1+x+x^2+x^3+\dots \right)}^3$

I will use the interpretation used in exercise 13: The number of different ways to give localid="1668661219427" $\mathrm{r}$identical balloons tolocalid="1668661227577" $\mathrm{n}$children where each child receives ... balloons.

$$\begin{gathered} n=3r \\ =4 \end{gathered}$$

Since the sum $1+x+x^2+x^3+\dots$contains all possible powers of x, there is no restriction on the number of balloons that each child has to receive.

The number of different ways to give 4 identical balloons to 3 children is represented by the given expansion.

The order of the balloons is not important.

Thus, by using the combination, repetition of the same children is also allowed:

$$\begin{gathered} C(3+4-1,4)=C(6,4) \\ =\frac{6!}{4!2!} \\ =15 \end{gathered}$$