3
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – JMoravitz Apr 16 at 23:13
  • 1
    $\begingroup$ 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$ $\endgroup$ – Henry Lee Apr 16 at 23:20
  • $\begingroup$ can you explain why is it x^11? $\endgroup$ – Mary Apr 16 at 23:24
  • $\begingroup$ @Mary Because $x^{21}x^{11}=x^{32}$ $\endgroup$ – Bernard Massé Apr 16 at 23:43
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – amd Apr 17 at 18:32
  • $\begingroup$ 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. $\endgroup$ – Mary Apr 17 at 19:10
  • 1
    $\begingroup$ @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$. $\endgroup$ – amd Apr 17 at 19:13
  • $\begingroup$ 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... $\endgroup$ – Mary Apr 17 at 19:19
  • 1
    $\begingroup$ @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. $\endgroup$ – amd Apr 17 at 19:21

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.