Balanced Parentheses

Question

I was wondering if anyone can answer me which is number of results generated in the backtracking solution for the next problem:

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"

There is a related post in stackoverflow: Generate balanced parentheses in java

My doubt if that if there is a formula that can give me the number of valid parentheses I can generate before compute them. for example:
- f(n):
- f(1) = 1
- f(2) = 2
- f(3) = 5
and so on..

Thank you.

Answer 1

The number expressions containing n pairs of parentheses which are correctly matched can be calculated via Catalan numbers. Quoting the relevant link from Wikipedia:

There are many counting problems in combinatorics whose solution is given by the Catalan numbers … Cn is the number of Dyck words of length 2n. A Dyck word is a string consisting of n X's and n Y's such that no initial segment of the string has more Y's than X's … Re-interpreting the symbol X as an open parenthesis and Y as a close parenthesis, Cn counts the number of expressions containing n pairs of parentheses which are correctly matched.

The nth Catalan number is given directly in terms of binomial coefficients by: