Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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. –  Chris Taylor May 10 '12 at 9:20
    
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. –  GEdgar May 10 '12 at 12:43
    
Differentiate $(1+x^5+x^7)^{20}$ 18 times and evaluate at 0. –  N. S. May 10 '12 at 15:05

3 Answers 3

up vote 5 down vote accepted

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?

share|improve this answer
1  
The OP was looking for a different approach to this one. –  Michalis May 10 '12 at 7:54
    
@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. –  Babak S. May 10 '12 at 9:50
    
@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. –  bgins May 10 '12 at 10:59
    
@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. –  Michalis May 10 '12 at 12:59
    
@Michalis: do you think Stanley's reciprocity theorem would give us anything? I didn't really see an advantage to it for this problem. –  bgins May 10 '12 at 14:09

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.