Help need with Catalan series.

Блог пользователя deinier

Автор deinier, 12 лет назад, По-английски

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;
       }
    }
 }

dp, catalan numbers, modulus

deinier
12 лет назад
6

Комментарии (6)

Написать комментарий?

imslavko

12 лет назад, # |

Catalan series can be calculated as $\text{[math]}$ , so you can fo anything you do with binomial coefficients, good luck!

→ Ответить

deinier

12 лет назад, # ^ |

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.

→ Ответить

imslavko

12 лет назад, # ^ |

You should know that C_2nⁿ is in fact $\text{[math]}$ , 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

→ Ответить

deinier

12 лет назад, # ^ |

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

→ Ответить

wackloner

12 лет назад, # |

← Rev. 4 →

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 C_n^k 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 :)