Coefficient of $x^n$ What is the coefficient of $x^n$ of this following expression:                            
$$(x+x^2+x^3+ \dots + x^r)^n$$
I tried it but failed. I know that it can be solved  by combinations but how? What is the theorem? Is it in generating functions?
 A: Here we suppose $r\geq 2$. We have
$$(x + x^2 + \cdots + x^r)^n$$
$$=x^n(1+x+\cdots+x^{r-1})^n$$
$$=x^n(1+xp(x))^n$$
where $$p(x) = 1 + x + \cdots + x^{r-2}.$$
Next we use the binomial theorem to write
$$=x^n(1+xp(x))^n$$
$$= x^n\left(\sum_{k=0}^n \binom{n}{k}x^kp(x)^k\right)$$
$$= \sum_{k=0}^n \binom{n}{k}x^{n+k}p(x)^k$$
and we see the coefficient of $x^n$ is $\binom n 0 = 1$.
A: $\newcommand{\+}{^{\dagger}}%
 \newcommand{\angles}[1]{\left\langle #1 \right\rangle}%
 \newcommand{\braces}[1]{\left\lbrace #1 \right\rbrace}%
 \newcommand{\bracks}[1]{\left\lbrack #1 \right\rbrack}%
 \newcommand{\dd}{{\rm d}}%
 \newcommand{\isdiv}{\,\left.\right\vert\,}%
 \newcommand{\ds}[1]{\displaystyle{#1}}%
 \newcommand{\equalby}[1]{{#1 \atop {= \atop \vphantom{\huge A}}}}%
 \newcommand{\expo}[1]{\,{\rm e}^{#1}\,}%
 \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,}%
 \newcommand{\ic}{{\rm i}}%
 \newcommand{\imp}{\Longrightarrow}%
 \newcommand{\ket}[1]{\left\vert #1\right\rangle}%
 \newcommand{\pars}[1]{\left( #1 \right)}%
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\pp}{{\cal P}}%
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,#2\,}\,}%
 \newcommand{\sech}{\,{\rm sech}}%
 \newcommand{\sgn}{\,{\rm sgn}}%
 \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}}
 \newcommand{\ul}[1]{\underline{#1}}%
 \newcommand{\verts}[1]{\left\vert #1 \right\vert}%
 \newcommand{\yy}{\Longleftrightarrow}$
It should ${\large\it obviously}$ be $\Huge 1$.
In general $\pars{~\mbox{we are assuming}\ r,n \geq 1~}$,
\begin{align}
&\pars{x + x^{2} + \cdots + x^{r}}^{n} = x^{n}\pars{1 + x + \cdots + x^{r - 1}}^{n}
=
x^{n}\pars{x^{r} - 1 \over x - 1}^{n} = x^{n}\pars{1 - x^{r}}^{n}\pars{1 - x}^{-n}
\\[3mm]&=
x^{n}\sum_{\ell = 0}^{\infty}{n \choose \ell}\pars{-1}^{\ell}x^{r\ell}
\sum_{\ell' = 0}^{\infty}{-n \choose \ell'}\pars{-1}^{\ell'}x^{\ell'}
\\[3mm]&=
x^{n}\sum_{\ell = 0}^{\infty}\sum_{\ell' = 0}^{\infty}
\pars{-1}^{\ell + \ell'}{n \choose \ell}{-n \choose \ell'}
\sum_{n' = 0}^{\infty}x^{n'}\delta_{n',r\ell + \ell'}
\\[3mm]&=
x^{n}\sum_{n' = 0}^{\infty}x^{n'}\sum_{\ell' = 0}^{\infty}
\pars{-1}^{\ell'}{-n \choose \ell'}
\sum_{\ell = 0}^{\infty}{n \choose \ell}\pars{-1}^{\ell}
\delta_{r\ell,n' - \ell'}
=
\sum_{n' = n}^{\infty}a_{n'}x^{n'}
\end{align}

$$
\pars{x + x^{2} + \cdots + x^{r}}^{n}
=
\sum_{n' = n}^{\infty}a_{n'}x^{n'}
$$
where $a_{n'}$ is given by:
$$
a_{n'}
=
\sum_{\ell' = 0}^{\infty}
\pars{-1}^{\ell'}{-n \choose \ell'}
\sum_{\ell = 0}^{\infty}
{n \choose \ell}\pars{-1}^{\ell}\delta_{r\ell,n' - n - \ell'}\,,
\qquad
n' \geq n
$$

\begin{align}
a_{n'}&=\sum_{\ell' = 0}^{\infty}{n + \ell' - 1 \choose \ell'}
{n \choose {n' - n - \ell' \over r}}\pars{-1}^{\pars{n' - n - \ell'}/r}
\\&\phantom{=}\mbox{where}\quad r \isdiv \pars{n' - n - \ell'}\quad\mbox{and}\quad
0 \leq {n' - n - \ell' \over r } \leq n\tag{1}
\end{align}
In $\pars{1}$, the second condition is equivalent to:
$$
n' -n\pars{1 + r} \leq \ell' \leq n' - n\ {\tt\large \geq 0}
$$
