Consider sequences of properly nested parentheses. By properly nested 
I mean that every left parenthesis has a matching right parenthesis
and that at every stage the number of left parantheses seen so far is
greater than or equal to the number of right parentheses. Write an
algorithm (pseudo-code) to determine the number of different possible
sequences of properly nested parentheses with N pairs of parentheses.
Another way of thinking of this is as follows. Consider an n+2 sides
convex polygon. In how many ways can it be cut into N triangles by
drawing non-intersecting diagonals?

The first few of these numbers are:
1,2,5,14,42,132

Here are the 5 possible sequences of properly nested parentheses for 3 pairs:

((()))   (())()  ()(())  (()())  ()()()

chuvak2k-ga,

The algorithm for determining this value is as follows:

function NPPermutations (int numP) {
	int permutations = 1
	for (int i=numP+2;i<=2*numP;i++) {
		permutations = permutations * i
	}
	for (int i=2;i<=numP;i++) {
		permutations = permutations / i
	}
	return permutations
}

(Source: http://planetmath.org/encyclopedia/CatalanNumbers.html)


Cheers,
tox-ga

---

Clarification of Answer by tox-ga on 03 Feb 2005 15:05 PST

chuvak2k-ga,

Please feel free to request a clarification if this is not exactly
what you are looking for.

Cheers,
tox-ga

---

Request for Answer Clarification by chuvak2k-ga on 03 Feb 2005 15:41 PST

How can I send you the $ ? I just rated the answer but it didnt pay you anything?

---

Clarification of Answer by tox-ga on 03 Feb 2005 16:56 PST

chuvak2k-ga,

Don't worry, it is all taken care of by Google Answers. For future
reference, once you have posted a question, the only thing you need to
concern yourself with is whether or not you wish to tip the answerer
for the response.


Cheers,
tox-ga

i will have to modify the answer abit, but this is what was needed.

I think what you are looking for are the Catalan numbers.

C_n = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!)

Eric W. Weisstein et al. "Catalan Number." From MathWorld--A Wolfram
Web Resource. http://mathworld.wolfram.com/CatalanNumber.html

Here is the Sloan link to the sequence
http://www.research.att.com/projects/OEIS?Anum=A000108

Is this helps?