# Another Trigonometry problem, sum of products of sine function over partitions of N

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

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

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