How many ways are there to parenthesise an expression?

Question

Context

I am writing a computer program to do a brute-force search for a solution to a puzzle which wanted to arrange four numbers with the four standard arithmetic operators and arrive at a given answer. While I have a solution to the original puzzle, I still want to write a general-case solving program for n numbers. I have broken down the problem into:

1. Arrangements of the numbers (n!)
2. Arrangements of operators (4^n-1)
3. Arrangements of associativity. Or bracketing, if you will.

It is this last one where I cannot find the general-case answer to "how many will there be?" but if I am to write a program to solve it then I need my test cases to prove that my implementation is correct.

Progress

I have a notation for these, which operates by breaking the formula under consideration into Reverse Polish notation, and expressing it as 1 for a "Push number" operation, or 0 for "Pop two numbers, apply operator, push result" operation. It is clear that the four operators are binary operators, so the first two operations must necessarily be "Push" operations. Similarly, the last one must be a calculation.

Further, when counting N₁ - the numbers of pushes - and N₀ - the numbers of calculations - from the start up to any given point, N₁ must always be greater than N₀

By inspection, I have determined the following results:

 n | C(n) | 
---+------+-
 2 |   1  | 110
 3 |   2  | 11010 11100
 4 |   5  | 1101010 1101100 1110010 1110100 1111000
 5 |  14  | 

I think C₆ is 42 but am not yet sure about that.

Question

What is the general-case value for C_n?

Answer 1

As Gerry pointed out in the comments, these are the Catalan numbers. The Wikipedia article has a section http://en.wikipedia.org/wiki/Catalan_number#Applications_in_combinatorics which includes, as one of its examples,

C_n is the number of different ways n + 1 factors can be completely parenthesized (or the number of ways of associating n applications of a binary operator).

which is exactly the case in the question. Indeed, the first example given in that article talks about

C_n 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.

which corresponds almost exactly to the observation in the OP in the results table under "Progress".

The answer is therefore

$$C_n = \frac{1}{(n+1)}.{2n \choose n} = \frac{(2n)!}{n!(n+1)!}$$

This then simply needs to be adapted to fit the needs of the original question as this yields the results $C_4 = 14$ whereas the question expressed its requirements such that $C_5 = 14$. The alternative is to adapt the question such that it considered the operators rather than the terms.