Coefficient of $x^{41}$ in $(x^5 + x^6 + x^7 + x^8 + x^9)^5$

Question

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?

Answer 1

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

Answer 2

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*}

Comment:

• 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

Answer 3

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}$$