@Nikhil: The number of valid parenthesizations of n pairs of parentheses is given by the nth Catalan Number. See http://en.wikipedia.org/wiki/Catalan_number to 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.