Tell me more ×
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.
up vote 1 down vote favorite
1

I don't know how to write the summation symbol so I'm providing you the original link to problem http://www.codechef.com/OCT11/problems/PARSIN .My approach to solve this problem is first reduce the expression sin(k1X) * sin(k2X) ..... *sin(kmX) to some terms where I can have k1+k2+....+km instead of their product.In doing so I don't need to find all possible combinations of (k1,k2,...,km).But not abled to do that.Can anyone please suggest any better ideas or at least tell me if I'm on a correct path or not ? For past three days I'm struggling with this problem and as my last hope I'm posting this problem here.Please help !!!!

share|improve this question
2  
Apparently you want compositions, not partitions. – J. M. Oct 5 '11 at 17:27
For the summation symbol, use \sum_{i=1}^k to get $\sum_{i=1}^k$ – Ross Millikan Oct 5 '11 at 17:35
Why don't you define the function recursively? Looking at the problem, this seems to me the natural thing to do. – Raskolnikov Oct 5 '11 at 17:35
@J.M. Compositions but how ? Are you applying composition for calculating sin(k1X)*sin(k2X)...*sin(kmX) ? Correct me if I'm wrong. – code_hacker Oct 5 '11 at 17:47
2  
$-1$:This is a problem from an ongoing contest in codechef.Discussing the solution now would be unfair.Please wait until the contest is over.Thanks. – Quixotic Oct 5 '11 at 19:23
show 5 more comments

1 Answer

up vote 1 down vote

The problem is to find the sum of $\quad \sin(k_1 x) \sin(k_2 x) \dots \sin (k_m x) \quad$ for all positive integer $m$-tuples $(k_1, \dots, k_m)$ with $\sum k_i = N$.

One way is to compute the generating function $f(t) = \sum \sin(kt)t^k$ (which is something like $\frac{\sin(x) t}{1 -2\cos(x)t + t^2}$), and the $t^N$ coefficient of $f(t)^m$.

Another is to use trigonometric formulas such as $\quad 2 \sin(a)\sin(b)=\cos(a+b) - \cos(a-b) \quad$ to handle the $m=2$ case which would then give a reduction from the $m$ to the $m-1$ case in general.

share|improve this answer
I'm finding first method somewhat difficult.Can you explain second method a bit more in detail? – code_hacker Oct 5 '11 at 18:52
In the second let $a = k_1 x$ and $b = k_2 x$ and consider a fixed value of $k_1 + k_2$. Then $a+b$ is constant for fixed $k_1 + k_2$ so one reduces $m$ by 1 for the part multiplying the $cos(a+b)$ term. The $(a-b)$ will run over an arithmetic progression of values (something like $cos(x)+cos(3x) + ...$) which also can be summed explicitly knowing $a+b$ and this again leads to a reduction of $m$. Also, you can try this for the entire set of possible (k1, k2) and maybe get a more direct reduction of order. – zyx Oct 5 '11 at 19:04

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.