2
$\begingroup$

I have the equation

$u_1 + u_2 + ... + u_5 = 24$

with the restrictions

$1 \le u_i \le 7, i = 1,...5$

I've managed to work up to the point of finding the coefficient of $x^{24}$ in

$(X+X^2+...X^7)^5 = X^5(1+X+...X^6)^5$

I know my final answer will need to be in binomial form similar to this $\binom{10}{5}$

However I am unsure where to go, or if this is even correct. Any help would be greatly appreciated.

$\endgroup$
  • 2
    $\begingroup$ Does it help (simplify the calculation, I mean) to write the GF as $X^5 \frac{(1-X^7)^{5}}{(1-X)^{5}}$ ? $\endgroup$ – ancientmathematician May 1 '17 at 9:35
  • $\begingroup$ @ancientmathematician I believe so! Would that correctly equate to $g(X)\sum_{i=0}^\infty \binom{5 + i -1}{i} X^i$? $\endgroup$ – Arnaud Van Wyk May 1 '17 at 10:14
  • $\begingroup$ Yes - the infinite sum is the binomial expansion of $(1-X)^{-5}$ so you have $g(X)=X^5(1-X^7)^5$. To find the coefficient of $X^{24}$ you will have to add three terms from this series. $\endgroup$ – gandalf61 May 1 '17 at 10:28
  • $\begingroup$ @gandalf61I'm very sorry, but I'm not entirely sure what you mean by this? Is this correct - $g(X) = 1 - 5X^7 + 10X^{14} - 10X^{21} + 5X^{28} - X^{35}$? Or have I made a mistake? $\endgroup$ – Arnaud Van Wyk May 1 '17 at 10:33
  • $\begingroup$ You're right but doing unnecessary work! To get 19 the only possibilities are (i) 0 from $g(X)$ and 19 from the $(1-X)^{-5}$; (ii) 7 from $g(X)$ and 12 from the $(1-X)^{-5}$ (iii) 14 from $g(X)$ and 5 from the $(1-X)^{-5}$. There's no need to work out any other term. $\endgroup$ – ancientmathematician May 1 '17 at 12:14
1
$\begingroup$

Everything is fine with your generating function. It is convenient to use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ in a series.

We obtain \begin{align*} [x^{24}]&(x+x^2+\cdots+x^7)^5\\ &=[x^{24}]x^5(1+x+\cdots+x^6)^5\\ &=[x^{19}]\left(\frac{1-x^{7}}{1-x}\right)^5\tag{1}\\ &=[x^{19}](1-x^7)^5\cdot\frac{1}{(1-x)^5}\\ &=[x^{19}](1-5x^{7}+10x^{14})\sum_{n=0}^\infty\binom{-5}{n}(-x)^n\tag{2}\\ &=\left([x^{19}]-5[x^{12}]+10[x^5]\right)\sum_{n=0}^\infty\binom{n+4}{4}x^n\tag{3}\\ &=\binom{23}{4}-5\binom{16}{4}+10\binom{9}{4}\tag{4}\\ &=1015 \end{align*}

Comment:

  • In (1) we use the geometric series formula and apply the rule \begin{align*} [x^{p-q}]A(x)=[x^p]x^qA(x) \end{align*}

  • In (2) we use the binomial series expansion and expand $(1-x^7)^5$. We skip terms with exponent $21$ and greater since they do not contribute to $[x^{19}]$.

  • In (3) we use the linearity of the coefficient of operator, apply again the rule as in (1) and we use the binomial identity $$\binom{-p}{q}=\binom{p+q-1}{p-1}(-1)^q$$

  • In (4) we select the coefficients accordingly.

$\endgroup$
  • $\begingroup$ This was an incredible help! Thank you! $\endgroup$ – Arnaud Van Wyk May 2 '17 at 2:27
  • $\begingroup$ @ArnaudVanWyk: You're welcome! Good to see the answer is useful. :-) $\endgroup$ – Markus Scheuer May 2 '17 at 6:32

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.