# Find the coefficient of $x^{32}$ in $(x^3 +x^4 +x^5 +x^6 +x^7)^7$

I don't understand the explanation in the book and why the final answer looks the way it does. I know I am supposed to factor and it will equal to $$(x^3(1+x+\cdots+x^4))^7$$. But after that, I am really confused about what happens. Can someone explain this problem step by step. Thank you!

• Continuing from where you left off, the question can be rephrased as to ask how many integral solutions there are to the system $\begin{cases} a_1+a_2+a_3+a_4+a_5 = 11\\ 0\leq a_i\leq 4\end{cases}$. If you don't feel like brute forcing it the rest of the way, I recommend using a mixture of stars-and-bars and inclusion-exclusion. – JMoravitz Apr 16 at 23:13
• As you said, it is equal to: $$\left[x^3(1+x+x^2+x^3+x^4)\right]^7$$ which we can rewrite as: $$x^{21}(1+x+x^2+x^3+x^4)^7$$ so you now want the coefficient of $x^{11}$ in $(1+x+x^2+x^3+x^4)^7$ – Henry Lee Apr 16 at 23:20
• can you explain why is it x^11? – Mary Apr 16 at 23:24
• @Mary Because $x^{21}x^{11}=x^{32}$ – Bernard Massé Apr 16 at 23:43

A strategy for solving problems like this one is to try to rewrite the expression as the quotient of a polynomial in $$x$$ and some power of $$1-x$$. You can then use either Newton’s generalized binomial theorem or the identity $${1\over(1-s)^{k+1}} = \sum_{n=0}^\infty \binom{n+k}k s^n$$ to expand the denominator as a power series and write the coefficient that you seek as a linear combination of a small number of binomial coefficients.

Before plunging into the calculations, a handy bit of notation: $$[x^n]f(x)$$ stands for “the coefficient of $$x^n$$ in the power series for $$f(x)$$.” The brackets “absorb” powers of $$x$$, that is, $$[x^n]x^mf(x) = [x^{n-m}]f(x)$$. Basically, pulling out a factor of $$x^m$$ lets you reduce the exponent in the bracket—the coefficients are shifted down $$m$$ places in what remains. Diving right in, then,

\begin{align} [x^{32}](x^3+x^4+x^5+x^6+x^7)^7 &= [x^{32}]\left(x^3(1+x+x^2+x^3+x^4)\right)^7 \\ &= [x^{32}]x^{21}(1+x+x^2+x^3+x^4)^7 \\ &= [x^{11}](1+x+x^2+x^3+x^4)^7 \\ &= [x^{11}]\left({1-x^5 \over 1-x}\right)^7 \\ &= [x^{11}]{\binom70-\binom71x^5+\binom72x^{10}-\dots \over (1-x)^7} \\ &= \binom70[x^{11}]{1\over(1-x)^7} - \binom71[x^6]{1\over(1-x)^7} + \binom72[x]{1\over(1-x)^7} \\ &= \binom70\binom{17}6 - \binom71\binom{12}6 + \binom72\binom{7}6 \\ &= 6055.\end{align}

The absorption rule is used in lines 3 and 6. When expanding the numerator using the binomial theorem in line five, we can ignore all terms that involve powers of $$x$$ greater than $$11$$ since they won’t contribute anything to the final result.

• If you need a shortcut for such calculations, try to spot the pattern in the arguments to the binomial coefficients in the next-to-last line. – amd Apr 17 at 18:32
• But how did you do the last step? Where does the 17C6 come from or the 12C6 come from? I learned the method of r+n-1 (hopefully the formula is correct). Yet I always get stuck to know where the r or n comes from. – Mary Apr 17 at 19:10
• @Mary I use the identity at the top of my answer: $[x^n]\frac1{(1-x)^{k+1}}=\binom{n+k}k$. Here, $k=6$, so for $n=11$, the coefficient is $\binom{11+6}6$. – amd Apr 17 at 19:13
• Where does the 6 come from? Isn't k suppose to be 7? How did k end up being 6 is what I don't get... – Mary Apr 17 at 19:19
• @Mary To reduce clutter on the right-hand side, the exponent on the left-hand side of that identity is expressed as $k+1$. In your problem, we need to find coefficients of $1/(1-x)^7$, so $k+1=7$. These $\pm1$ adjustments crop up pretty often in combinatorial identities. I often have to double-check my own work to make sure that I’ve gotten them right. – amd Apr 17 at 19:21