deinier's blog

Help need with Catalan series.
By deinier, 13 years ago, In English

Hi, everyone. I want to know if the i — term (mod 1000000007) to the Catalan series could be calculated by this way. Do you, please, can explain me, if this way I get the answer by dp or if I need to do other thing? Thanks everybody. 

fact[1][1] = 1;
for(i=2;i<=1000;i++)
 {
   for(j=1;j<=i;j++)
    {
      if(j == 1)
        fact[i][1] = 1;
      else
       {
         if(i == j)
           fact[i][j] = fact[i][j-1] + fact[i-1][j-1];
         else
           fact[i][j] = fact[i][j-1] + fact[i-1][j];
         fact[i][j] %= 1000000007;
       }
    }
 }
  • Vote: I like it
  • +1
  • Vote: I do not like it

»
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Catalan series can be calculated as , so you can fo anything you do with binomial coefficients, good luck!

→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks, man, I read about that too, but I need to know too what is the problem to use this way because I think it give me the numbers too. I appreciate your help. I will study with binomial coefficients.

    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      You should know that C2nn is in fact , so you can calculate both parts (take reminder of both) and divide first by second. Get reminder of such operation you can using your math, or simply multiply them and reverse element.

      Sorry for poor English, but I don't know how to explain it in English

      → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        No problem man, my first language is Spanish. Thank very much!!!

        → Reply
»
13 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Some days ago i was thinking about it. And i made my own code:

long Catalan(int n) {
        long res = C(2*n, n);
	res /= n + 1;
	return res;
}

long C(int n, int k) {
	long res = 1;
	for (int i = 1; i <= k; i++)
		res = res * (n - k + i) / i;
	return res;
}

As you can see, for calculating Catalan series I chose formula .
And for calculating Cnk I chose optimazed realization of standart algorithm.
I think my code may help you. If not, I won't be offended :) Have a good time :)

→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Thanks man, I appreciate that too. I will try to prove my solution in other exercise. Have a nice day!!!

    → Reply