Finding a coefficient of $x^{57}$ in a polynomial $(x^2+x^7+x^9)^{20}$

Question

So the task is to find a coefficient of $x^{57}$ in a polynomial $(x^2+x^7+x^9)^{20}$

I was wondering if there is a more intelligible and less exhausting strategy in finding the coefficient, other than saying that $(x^2+x^7+x^9)^{20}=((x^2+x^7)+x^9)^{20}$ and then working with binomial expansion.

Answer 1

There is a thing called multinomial theorem which is a slight generalization of the binomial theorem.

First of all, note $(x^2+x^7+x^9)^{20}= x^{40}(1+x^5+x^7)^{20}.$ So, basically, now will find the coefficients of $x^{17}.$ Can you continue?

Note that $(1)^{17} (x^5)^2(x^7)^1$ gives us $x^{17}.$ The coffocient of $x^{17}$ is $\dfrac{20!}{17! 2! 1!}$.

The idea of binomial/multinomial theorem is purely combinatorial.

Suppose we have $(x+y+z)^{20}.$ Consider the term $x^{10}y^{6}z^{4}.$ Note that the coefficient of this term is $\dfrac{20!}{10! 6! 4!}$ The combinatorial interpretation is that you can create/form the $x^{10}y^{6}z^{4}$ $\dfrac{20!}{10! 6! 4!}$ ways. This should you give you some idea to think more about the problem. I hope it helps.

Answer 2

$x^{40}(1+x^5+x^7)^{20}=x^{40}(1+x^5(1+x^2))^{20}=$

$x^{40}(1+20x^5(1+x^2)+$

$(20)(19)/2![(x^5)(1+x^2)]^2+$

$(20)(19)(18)/3![x^5(1+x^2)]^3+..).$

Need the coefficient of $x^{17}$ in the above expansion.

Which term is relevant?

Answer 3

Rewrite as $x^{40}((1+x^5)+x^7)^{20}$, then the k-th term of the binomial expansion (ignoring the $x^{40}$) is $\binom{20}kx^{7(20-k)}\sum_{i=0}^k \binom kix^{5i}$.

We now actually want the exponent to be 17. Check $i=0, 1, 2, 3$ to see the only possibility is $i=2$, which gives $k=19$.

Hence the coefficient is $\binom{20}{19}\binom{19}2=3420.$

Answer 4

$$ \begin{align} \left[x^{57}\right]\left(x^2+x^7+x^9\right)^{20} &=\left[x^{57}\right]\sum_{\substack{a+b+c=20\\a,b,c\ge0}}\frac{20!}{a!\,b!\,c!}x^{2a+7b+9c}\tag1\\ &=\sum_{\substack{2a+7b+9c=57\\a+b+c=20\\a,b,c\ge0}}\frac{20!}{a!\,b!\,c!}\tag2\\ &=\sum_{\substack{5b+7c=17\\b,c\ge0}}\frac{20!}{(20-b-c)!\,b!\,c!}\tag3\\[3pt] &=\frac{20!}{(20-2-1)!\,2!\,1!}\tag4\\[15pt] &=3420\tag5 \end{align} $$ Explanation:
$(1)$: apply the Multinomial Theorem
$(2)$: extract the coefficient of $x^{57}$
$(3)$: substitute $a=20-b-c$
$(4)$: the only non-negative solution to $5b+7c=17$ is $(b,c)=(2,1)$
$(5)$: evaluate