What is the coefficient of $x^5$ in $(1+x+x^2+x^3+x^4+x^5)^{17}$?

Question

I figured that $(1+x+x^2+x^3+x^4)^{17} = (1-x^6)^{17}*(1-x)^{-17}$ but don't know what else to do.

I would really appreciate any help

Answer 1

You can pick up an $x^5$ from one term and a $1$ from every other term 17 different ways.

You can pick up an $x^4$ from one term, an $x$ from a second term in $\dfrac{17!}{15!}$ ways.

You can get $x^3$ and $x^2$ in $\dfrac{17!}{15!}$ ways.

You can get $x^3$, $x$, $x$ in $\dfrac{17!}{1!2!14!}$ ways.

You can get $x^2, x^2, x$ in $\dfrac{17!}{1!2!14!}$ ways.

You can get $x^2,x,x,x$ in $\dfrac{17!}{1!3!13!}$ ways.

And finally, you can get $x,x,x,x,x$ in $\dbinom{17}{5}$ ways.

Show that this is exhaustive, and it should give you the correct answer.

Final tally:

$$17+2\cdot \dfrac{17!}{15!} + 2\cdot \dfrac{17!}{2!14!} + \dfrac{17!}{3!13!} + \dfrac{17!}{5!12!} = 20,349$$

Answer 2

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ \begin{align} &\bbox[10px,#ffd]{% \bracks{x^{5}}\pars{1 + x + x^{2} + x^{3} + x^{4} + x^{5}}^{17}} = \bracks{x^{5}}\pars{1 - x^{6}}^{17}\pars{1 - x}^{-17} \\[5mm] = &\ \bracks{x^{5}}\pars{1 - x}^{-17} = {-17 \choose 5}\pars{-1}^{5} = -\bracks{{-\pars{-17} + 5 - 1 \choose 5}\pars{-1}^{5}} \\[5mm] = &\ {21 \choose 5} = \bbx{20349} \end{align}

Answer 3

Another combinatorial approach:

When you multiply it out, each term is of the following form:

$$x^{a_1}x^{a_2}\cdots x^{a_{17}} = x^{a_1+a_2+\cdots + a_{17}}$$

You are looking for the number of solutions to $a_1+a_2+\cdots + a_{17} = 5$ where $\forall i: 0\le a_i \le 5$. Since the sum must add to 5 and there are no negatives, this is automatically satisfied, so we can ignore the upper bounds (a solution with no upper bounds is the same as a solution with upper bounds of 5 for each factor).

This is a well-known problem. It is the number of nonnegative integral solutions to a Diophantine equation. The solution is $$\dbinom{5+17-1}{5} = \dbinom{21}{5}$$

Answer 4

Since $$ \left( {1 + x + x^2 + x^3 + x^4 } \right)^{\,17} = \left( {{{1 - x^5 } \over {1 - x}}} \right)^{\,17} $$ you might be interested to know that the general case of what are somewhere called r-nomial coefficients corresponds to the O.G.F: $$ F_b (x,r,m) = \sum\limits_{0\,\, \leqslant \,\,s\,\,\left( { \leqslant \,\,r\,m} \right)} {N_b (s,r,m)\;x^{\,s} } = \left( {1 + x + \cdots + x^{\,r} } \right)^m = \left( {\frac{{1 - x^{\,r + 1} }}{{1 - x}}} \right)^m $$ where $$ N_b (s,r,m)\quad \left| {\;0 \leqslant \text{integers }s,m,r} \right.\quad = \sum\limits_{\left( {0\, \leqslant } \right)\,\,k\,\,\left( { \leqslant \,\frac{s}{r+1}\, \leqslant \,m} \right)} {\left( { - 1} \right)^k \binom{m}{k} \binom { s + m - 1 - k\left( {r + 1} \right) } { s - k\left( {r + 1} \right)}\ } $$

You can find a full explanation in this related post and in this paper

In your particular case, if it is $(1+ \cdots+x^4)^{17}$ $$ \eqalign{ & N_b (5,4,17)\quad = \sum\limits_{\left( {0\, \le } \right)\,\,k\,\,\left( { \le \,{s \over {r + 1}}\, \le \,m} \right)} {\left( { - 1} \right)^k \left( \matrix{ 17 \cr k \cr} \right)\left( \matrix{ 21 - 5k \cr 5 - 5k \cr} \right)} = \cr & = \left( \matrix{ 17 \cr 0 \cr} \right)\left( \matrix{ 21 \cr 5 \cr} \right) - \left( \matrix{ 17 \cr 1 \cr} \right)\left( \matrix{ 16 \cr 0 \cr} \right) = \left( \matrix{ 21 \cr 5 \cr} \right) - 17 = 20322 \cr} $$ or for $(1+ \cdots+x^5)^{17}$ $$ \eqalign{ & N_b (5,5,17)\quad = \sum\limits_{\left( {0\, \le } \right)\,\,k\,\,\left( { \le \,{s \over {r + 1}}\, \le \,m} \right)} {\left( { - 1} \right)^k \left( \matrix{ 17 \cr k \cr} \right)\left( \matrix{ 5 + 17 - 1 - 6k \cr 5 - 6k \cr} \right)} = \cr & = \sum\limits_{\left( {0\, \le } \right)\,\,k\,\,\left( { \le \,{s \over {r + 1}}\, \le \,m} \right)} {\left( { - 1} \right)^k \left( \matrix{ 17 \cr k \cr} \right)\left( \matrix{ 21 - 6k \cr 5 - 6k \cr} \right)} = \left( \matrix{ 21 \cr 5 \cr} \right) = 20349 \cr} $$

Answer 5

It is equivalent to the problem: how many ways can $5$ candies be distributed among $17$ children? Mathematically, it is: $$x_1+x_2+\cdots +x_{17}=5, 0\le x_i\le 5, i=1,2,...,17.$$ The partitions of $5$ are: $$\begin{align}\{5\} &\Rightarrow P(17,1)=\frac{17!}{16!}=17\\ \{4,1\} &\Rightarrow P(17,2)=\frac{17!}{15!}=272\\ \{3,2\}&\Rightarrow P(17,2)=\frac{17!}{15!}=272\\ \{3,1,1\}&\Rightarrow \frac{P(17,3)}{2!}=\frac{17!}{2\cdot 14!}=2040\\ \{2,2,1\}&\Rightarrow \frac{P(17,3)}{2!}=\frac{17!}{2\cdot 14!}=2040\\ \{2,1,1,1\}&\Rightarrow \frac{P(17,4)}{3!}=\frac{17!}{6\cdot 13!}=9520\\ \{1,1,1,1,1\}&\Rightarrow \frac{P(17,5)}{5!}=\frac{17!}{120\cdot 12!}=6188\\ \end{align}$$ Hence, the sum is: $20,349$.