4
$\begingroup$

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.

  • 5
    For this specific question the answer is zero, since none of 18, 11 or 4 are multiples of 5. This doesn't work for the more general case, however.2012-05-10
  • 0
    How about an off-the-wall method: compute the coefficient by Cauchy's theorem, using a certain contour integral ... which we can compute numerically, knowing the result is an integer we only have to get it within 0.5 ... I haven't actually written it down yet.2012-05-10
  • 0
    Differentiate $(1+x^5+x^7)^{20}$ 18 times and evaluate at 0.2012-05-10

3 Answers 3

5

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. = ZZ['t'] p = (1+t^5+t^7)^20 p[18] 

Do you really want to find another way?

  • 2
    The OP was looking for a different approach to this one.2012-05-10
  • 0
    @bgins: Thanks bgins for the answer. I think, finding another way for this problem is somhow improffesional. What was said about it is enough. Thanks again.2012-05-10
  • 0
    @Michalis: of course you're right. I was offering (1) the obvious combinatorial interpretation, which actually solves the particular problem immediately with a minute's thought, (2) a technique to solve similar problems; and (3) the opinion that the poster may not want or need to delve further. I'd still be very curious, myself, to see what other methods are fruitful.2012-05-10
  • 0
    @bgins: Sure, your solution is definitely a straightforward and generally applicable one. I would also like to see a new approach though. I failed to find one.2012-05-10
  • 0
    @Michalis: do you think [Stanley's reciprocity theorem](http://en.wikipedia.org/wiki/Stanley%27s_reciprocity_theorem) would give us anything? I didn't really see an advantage to it for this problem.2012-05-10
2

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$:

enter image description here

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

1

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 $.