University of South Carolina High School Math Contest/1993 Exam/Problem 8

Problem

What is the coefficient of $x^3$ in the expansion of

$(1 + x + x^2 + x^3 + x^4 + x^5 )^6?$
$\mathrm{(A) \ } 40 \qquad \mathrm{(B) \ }48 \qquad \mathrm{(C) \ }56 \qquad \mathrm{(D) \ }62 \qquad \mathrm{(E) \ } 64$

Solution

If we expand out the given product, we see that we have a sum of terms in which each term is a product of six members of the set $\{1, x, x^2, x^3, x^4, x^5\}$ (with repetitions allowed). In order to have one of these terms equal to $x^3$, we can either have a single $x^3$ term and five terms of 1 in our product ($6\choose 1$ ways) or one $x^2$ term, one $x$ term and four 1 terms ($6\cdot 5$ ways) or have three $x$ terms ($6\choose 3$ ways). This gives us a total of ${6\choose 1} + 6\cdot 5 + {6\choose 3} = 6 + 30 + 20 = 56 \Longrightarrow \mathrm{(C)}$.