What is the coefficient of coefficient of $x^{41}$ in $(x^5 + x^6 + x^7 + x^8 + x^9)^5$?

Using summation of G.P., this is equivalent to finding the coefficient of $x^{41}$ in

$$\left(x^5 \left(\frac{1-x^5}{1-x}\right)\right)^5$$

and thus finding coefficient of $x^{16}$ in $(\frac{1-x^5}{1-x})^5$. How to proceed after this?


3 Answers 3


In other words, how many ways are there to write $$ 41 = a + b+c+d+e $$ where $a,b,c,d,e$ are integers between $5$ and $9$, inclusive.

The highest sum we can make is $9\cdot 5=45$, so to get $41$ instead we need to remove $4$ units from among the 5 variables. Fortunately, even removing all $4$ of them from the same variable still leaves $5$, which is a valid value. So what we're counting is the same as

How many ways are there to write $4$ as an (ordered) sum of $5$ non-negative integers?

This is a standard combinatorial problem; by the stars-and-bars formula, the answer is $$\binom{4+5-1}{4} = 70$$

  • $\begingroup$ A useful reduction to a simpler problem :-) $\endgroup$ Jul 12, 2016 at 13:21
  • $\begingroup$ I am sorry I don't follow this solution. How does a polynomial problem reduces to a permutation-combination problem? $\endgroup$
    – MonK
    Jul 12, 2016 at 13:29
  • 2
    $\begingroup$ @MonK: If you multiply out $(x^5+\cdots+x^9)^5$ but don't collect like terms, you get $5^5$ terms of the forrm $x^ax^bx^cx^d x^e$, where each exponent is in $\{5,6,7,8,9\}$ -- one term for each possible combination of $a,b,c,d,e$. After collecting like terms, the coefficient of $x^{41}$ is exactly the number of those terms that have $a+b+c+d+e=41$. $\endgroup$ Jul 12, 2016 at 13:49

It's convenient to use the coefficient of operator $[x^k]$ to denote the coefficient of $x^k$ in a series. This way we can write e.g. \begin{align*} [x^k](1+x)^n=\binom{n}{k} \end{align*}

We obtain \begin{align*} [x^{16}]\left(\frac{1-x^5}{1-x}\right)^5 &=[x^{16}](1-x^5)^5\sum_{k=0}^\infty \binom{-5}{k}(-x)^k\tag{1}\\ &=[x^{16}](1-5x^5+10x^{10}-10x^{15})\sum_{k=0}^\infty \binom{k+4}{4}(-x)^k\tag{2}\\ &=\binom{20}{4}-5\binom{15}{4}+10\binom{10}{4}-10\binom{5}{4}\tag{3}\\ &=4845-5\cdot 1365+10\cdot 210-10\cdot 5\\ &=70 \end{align*}


  • In (1) we use the binomial series expansion of $\frac{1}{(1-x)^5}$

  • In (2) it is sufficient to expand to binomial up to $x^{15}$ since we only need coefficients of powers of $x^{16}$. We also use the binomial identity \begin{align*} \binom{-n}{k}=\binom{n+k-1}{k}(-1)^k \end{align*}

  • In (3) we select the coefficients of the series accordingly

Why not to apply the multinomial sum (just to study it a little bit) so we need the coefficient of $x^{16}$ in $(x^4+x^3+x^2+x+1)^5$?

Put $A=x^3+x^2+x+1$ so one has $$(x^4+A)^5=x^{20}+5x^{16}A+10x^{12}A^2+10x^8A^3+5x^4A^4+A^5$$ Hence, after to see in $A,A^2,A^3,A^4$ ($A^5$ does not participate here because its greatest exponent is $15$) the coefficients of $1,x^4,x^8,x^{12}$ respectively, the required coefficient is equal to $$\color{red}{5\cdot1+10\cdot3+10\cdot3+5\cdot1=70}$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.