The coefficient of $x^{18}$ in $(1+x^5+x^7)^{20}$

I was asked about a simple question that is: “What is the coefficient of $x^{18}$ in $(1+x^5+x^7)^{20}$? Generally, we know that; $$(x+y+z)^n= \sum_{n_{1}+n_{2}+n_{3}=n}\left(\frac{n!}{n_{1}!n_{2}!n_{3}!}\right)x^{n_{1}} y^{n_{2}}z^{n_{3}}$$
So, this question could be answered easily based on above formula. May I ask, if we can find another way for solving such this problem or not. Thanks for sharing the thoughts.

Solutions Collecting From Web of "The coefficient of $x^{18}$ in $(1+x^5+x^7)^{20}$"

In solving the related combinatorics problems, it’s often easiest to program the polynomial multiplication using the simple expansion rule and then iteratively multiplying to get the answer, or just use a computer algebra system such as sage, maple, or mathematica. In your case, the multinomial theorem gives us
$$\left(1+x^5+x^7\right)^{20}=\sum_{n_1+n_2+n_3=20}{20\choose n_1,n_2,n_3}x^{5n_2+7n_3}$$
so the coefficient of $x^{18}$ is just the cardinality of
$$\left\{(n_1,n_2,n_3)\in\mathbb{Z}^3 \mid 0\le n_i ,~n_1+n_2+n_3\le20 ,~5n_2+7n_3=18\right\} \,,$$
i.e., the number of ways of writing $18$ as a sum of up to twenty $5$s and $7$s,
which is what I was calling the related combinatorics problem. In this case, the coefficient is zero because $18$ can’t be written as a sum of $5$s and $7$s — one of $12$ ($=\frac{(5-1)(7-1)}{2}$ being the genus of the numerical semigroup $\left<5,7\right>$) such positive integers.

For example, in sage, you can solve this quite simply:

R.<t> = ZZ['t']
p = (1+t^5+t^7)^20
p[18]


Do you really want to find another way?

OK you asked for something different. It turns out that this is not very practical. Your coefficient is
$$\frac{1}{2\pi i}\oint_C \frac{(1+z^5+z^7)^{20}}{z^{19}}\,dz$$
where $C$ is a curve in the complex plane that surrounds $0$ once in the positive direction. If we use the unit circle parameterized as $\exp(i t)$ with $0 \le t \le 2\pi$, this becomes
$$\frac{1}{2\pi}\int_0^{2\pi}\left(1+ e^{i 5 t}+e^{i 7 t}\right)^{20}e^{-i 18 t}\,dt .$$
In fact Maple computes this almost instantly as $0$, but presumably by multiplying out the trinomial, which is what we are supposed to avoid.

We can try an approximate numerical evaluation of the integral, and use the fact that it is an integer so that we only have to get within $0.5$ of the answer. But in fact that will mean using around 500 intervals in Simplson’s Method, since our integrand is quite oscillatory.

Just for fun, here is a complex plot of $1+ e^{i 5 t}+e^{i 7 t}$ with $0 \le t \le 2\pi$:

Our integrand gets as big as $3^{20}$ in absolute value…

Not really too different than the standard solution, but here is an idea: You can use only the binomial theorem:

$$(1+x^5+x^7)^{20}=\sum_{k=0}^{20} \binom{20}{k} 1^{20-k}(x^5+x^7)^k=\sum_{k=0}^{20} \binom{20}{k} x^{5k}(1+x^2)^k$$

Now, you can ignore the terms $k \geq 4$, because $x$ appears to a power of at least 20. You can also ignore the case $k \leq 2$ because $x$ will appear to a power at most $7*k <18$.

Thus, the coefficient of $x^{18}$ in $(1+x^5+x^7)^{20}$ is exactly the coefficient of $x^{18}$ in $\binom{20}{3} x^{15}(1+x^2)^3$.