coefficient of $x^{29}$ in the expansion of $(1+x^5+x^7+x^9)^{1000}$

Question

How can I use the multinomial theorem approach here??

Or is there any other method?

Coefficient of $x^{29}$ in the expansion of $(1+x^5+x^7+x^9)^{1000}$

Answer 1

Hint:

If you are open for more advanced methods than multinomial theorem, then you can make an unnormalized Markov chain with hmm.. 30 something states should be enough.

Find it's matrix and take it to the 1000th power times the $[1,0,0,\cdots,0]^T$ vector.

Or maybe diagonalize it or find other suitable canonical form first, to speed up calculations.

Calculating this in Matlab / GNU Octave

v = M^1000*[1;zeros(30,1)]

gives

$$v(30) = 1.237543687530000 \cdot 10^{14}$$

Which (given that the other answers are indeed correct) means we did not even break the numerical imprecision of our floating point model.

Answer 2

By multinomial expansion: $$\sum \frac{1000!}{a! b! c! d!} (x^5)^a (x^7)^b (x^9)^c (1)^d,~ where~ a+b+c+d=1000~ and ~5a+7b+9c=29.$$ There are two possibilities, $a=4, b=0, c=1, d=995$ and $a=3, b=2, c=0,d=995$ So the required co-efficient is $$\frac{1000!}{4!~ 1!~995!}+ \frac{1000!}{3!~ 2!~995!}= (\frac{1}{4!}+\frac{1}{3!~2!})\times\frac{1000!}{995!} = \frac{1000!}{8~(995!)}=123754368753000 . $$ Click below to see the expansion of $(1+x^5+x^7+x^9)^{1000}$ in Mathematica.

]1]1

Answer 3

Repeated Binomial Theorem $$ \begin{align} \left(1+x^5+x^7+x^9\right)^{1000} &=\sum_i\binom{1000}{i}\left(x^5+x^7+x^9\right)^i\\ &=\sum_i\binom{1000}{i}x^{5i}\left(1+x^2+x^4\right)^i\\ &=\sum_{i,j}\binom{1000}{i}\binom{i}{j}x^{5i}\left(x^2+x^4\right)^j\\ &=\sum_{i,j}\binom{1000}{i}\binom{i}{j}x^{5i+2j}\left(1+x^2\right)^j\\ &=\sum_{i,j,k}\binom{1000}{i}\binom{i}{j}\binom{j}{k}x^{5i+2j+2k}\\ \end{align} $$ Choosing all $5i+2j+2k=29$ where $i\ge j\ge k\ge0$ limits the sum greatly (two terms, to be precise) $$ \begin{align} \left[x^{29}\right]\left(1+x^5+x^7+x^9\right)^{1000} &=\binom{1000}{5}\binom{5}{2}\binom{2}{0}+\binom{1000}{5}\binom{5}{1}\binom{1}{1}\\[6pt] &=123754368753000 \end{align} $$ For me, it was easier to make sure that I got all the terms this way rather than the Multinomial approach.

Answer 4

Hint: How many ways can you form $29$ by adding together copies of $0,5,7,9$ so that you have $1000$ summands? Note that you need not consider more than four nonzero summands since $4×9$ is already $36,$ which has exceeded $29.$ Thus, the problem reduces to how many ways to form $29$ using at most four copies of the numbers $5,7,9.$