# Coefficient of $x^i$ in $(x+x^2+...+x^k)^n$

Is there any general way to find coefficient of $$x^i$$ in $$(x+x^2+...+x^k)^n$$

It is easy to solve when k is small like $$k=3$$ or $$k=4$$ by using multinomial coefficient

But how can we solve a problem: find coefficient of $$x^{50}$$ in the expansion of $$(x+x^2+...+x^{20})^{10}$$

Any help would be appreciated.

• This paper by Euler may be relevant: arxiv.org/abs/math/0505425.
– Art
May 3, 2020 at 19:02
• Although the paper I've linked above deals with polynomials of the form $(1 + x + x^2 + \dots + x^k)^n$, I think the polynomials in your question can be converted to this form by factoring out $x^n$. The final expression would then look like $x^n\cdot (1+x+x^2+\ldots+x^{k-1})^n$.
– Art
May 4, 2020 at 8:52
• @Art this transform just makes the polynomial similar to the paper you've linked above. anyway, thank you very much for the really cool paper May 4, 2020 at 12:02

Hint: Write the polynomial as $$x^n\cdot (1-x^{k})^n\cdot (1-x)^{-n}\tag 1$$ then take the convolution of the generating functions for the last two factors: \begin{align} (1-x^k)^n&=\sum_{j=0}^n \binom{n}j(-1)^j x^{kj},\\ (1-x)^{-n}&=\sum_{j=0}^\infty \binom{-n}j(-1)^j x^j=\sum_{j=0}^\infty \binom{n+j-1}{n-1} x^j\tag 2 \end{align} You want the coefficient of $$x^i$$ in $$(1)$$, which is the same as the coefficient of $$x^{i-n}$$ in the product of the series in $$(2)$$.

Edit: To explain the part about $$\binom{-n}j$$. Note that when $$n$$ is positive, we have the usual formula $$\binom{n}k=\frac{n(n-1)\dots (n-k+1)}{k!}$$ What is nice about the expression on the right is that it makes sense for negative (or even complex) $$n$$. When you substitute a negative value for $$n$$, you get \begin{align} \binom{-n}{k} &=\frac{(-n)(-n-1)\cdots (-n-k+1)}{k!} \\&=(-1)^k\frac{n(n+1)\cdots (n+k-1)}{k!} \\&=(-1)^k\binom{n+k-1}{k} \end{align} Furthermore, this natural generalization also agrees nicely with the binomial theorem. With this definition, it turns out that the Taylor series expansion $$(1+x)^n=\sum_{k=0}^\infty \binom{n}k x^k$$ holds when $$n$$ is negative, or even complex. These two points justify $$(2)$$.

• could you explain why $\binom{-n}{j}(-1)^j = \binom{n+j-1}{n-1}$ ? May 4, 2020 at 2:57
• in $(2)$, when we multiply 2 bionomials, there are numerous sets of $(a,b)$ for $x^{ka}.x^b=x^{i-n}$, does that mean we have to find entire sets? (sorry for the late reply) May 4, 2020 at 12:30
• @Becker Exactly. The result is a sum of products of several pairs of binomial coefficients. May 4, 2020 at 17:28
• The sums have a nice combinatorial interpretation: For $(1+x+x^2)^n$ (i.e, $k = 2$), the coefficients of $x^j$ look like $\sum_{i=0}^{\infty} {\binom{n}{k-i} \cdot \binom{k-i}{i}}$. This problem is equivalent to the problem "Given $j$ balls and $n$ bins, how many ways can you distribute the balls between the bins, such that no bin contains more than $2$ balls?". The sum above can be interpreted as "Choose $k-i$ bins out of $n$, and out of these chosen bins, choose $i$ bins to contain exactly $2$ balls (the rest of the chosen bins, therefore, contain only one ball). Repeat for all i."
– Art
May 5, 2020 at 8:10

Hint:

Can you relate your question to this problem:

How many solution does the equation $$t_1+t_2+...+t_{10}=50$$ have, Where $$1\leq t_1,t_2,...t_{10}\leq20$$

• your hint is exactly my original problem. I used generating function to find coefficient of $x^{50}$ May 3, 2020 at 5:52
• The hint maybe clever but far from being helpful for someone who does not know the concept behind it! At least I guess so. Nov 17, 2023 at 22:28