1
$\begingroup$

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

  • 0
    yeah I think you are right but after struggling with the problem for so many days,I just can't resist myself from discussing the approach for this problem but I'll keep your suggestion in mind.2011-10-06

1 Answers 1

1

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.

  • 0
    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.2011-10-05