7
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ This paper by Euler may be relevant: arxiv.org/abs/math/0505425. $\endgroup$
    – Art
    May 3, 2020 at 19:02
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Art
    May 4, 2020 at 8:52
  • $\begingroup$ @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 $\endgroup$
    – Becker
    May 4, 2020 at 12:02

2 Answers 2

6
$\begingroup$

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)$.

$\endgroup$
4
  • $\begingroup$ could you explain why $\binom{-n}{j}(-1)^j = \binom{n+j-1}{n-1}$ ? $\endgroup$
    – Becker
    May 4, 2020 at 2:57
  • $\begingroup$ 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) $\endgroup$
    – Becker
    May 4, 2020 at 12:30
  • 1
    $\begingroup$ @Becker Exactly. The result is a sum of products of several pairs of binomial coefficients. $\endgroup$ May 4, 2020 at 17:28
  • 2
    $\begingroup$ 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." $\endgroup$
    – Art
    May 5, 2020 at 8:10
0
$\begingroup$

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$

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .