if you are doing the codechef problem ..... http://www.codechef.com/problems/DCE03/
then using the following relation for finding catalan numbers will be easier since you need to find the answer mod(something)... C(n+1)=sumation(i=0 to n) C(i)*C(n-i) On Oct 1, 8:25 am, Dave <dave_and_da...@juno.com> wrote: > @Nikhil: The number of valid parenthesizations of n pairs of > parentheses is given by the nth Catalan Number. > Seehttp://en.wikipedia.org/wiki/Catalan_numberto validate this > statement. It is the first bullet point in "Applications in > combinatorics." Just let X = "(" and Y = ")". > > Furthermore, a simple recurrence relationship is given: > > C(0) = 1 > C(n+1) = 2*(2*n+1)*C(n)/(n+2), n >= 0. > > Dave > > On Sep 30, 1:56 pm, Nikhil Jindal <fundoon...@yahoo.co.in> wrote: > > > > > Try this: > > > Find the number of ways for generating n pairs of valid parenthesis. > > A set of parenthesis is said to be valid if at any instant while scanning > > from left to right, the number of opening parenthesis are never less than > > the number of closing parenthesis. > > > For ex: for n=3, f(n) = 5 > > > ()()(), ((())), (()()), ()(()), (())() > > > Cheers > > Nikhil Jindal > > > Please access the attached hyperlink for an important electronic > > communications > > disclaimer:http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
