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

  • 2
    Apparently you want [compositions](http://mathworld.wolfram.com/Composition.html), not partitions.2011-10-05
  • 0
    For the summation symbol, use \sum_{i=1}^k to get $\sum_{i=1}^k$2011-10-05
  • 0
    Why don't you define the function recursively? Looking at the problem, this seems to me the natural thing to do.2011-10-05
  • 0
    @J.M. Compositions but how ? Are you applying composition for calculating sin(k1X)*sin(k2X)...*sin(kmX) ? Correct me if I'm wrong.2011-10-05
  • 0
    You might want to see [this book](http://www.math.upenn.edu/~wilf/website/CombAlgDownld.html), BTW...2011-10-05
  • 0
    @Raskolnikov How can we apply recursion for this.I have studied recursion which says you must have some base condition and some recursive formula for the function,but here I don't have those formula and conditions.2011-10-05
  • 0
    You can make a recursive formula since $f(M,N,X) = \sum_{k} f(1,k,X) f(M-1,N-k,X)$.2011-10-05
  • 0
    The summation symbol in TeX is \sum or \Sigma (capital S in the second one). I wrote the problem statement with TeX in the answer below.2011-10-05
  • 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.2011-10-05
  • 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
    I'm finding first method somewhat difficult.Can you explain second method a bit more in detail?2011-10-05
  • 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