calculating the ways of parenthesizing a boolean expression

Question

Calculating the number of ways of parenthesizing a boolean expression. For example, a boolean expression I mean something like this, 1^0|0|1, for operator, it could be ^, & or |.

Did some reference and calculation, and it seems the number of ways is always (2n)!/((n+1)!n!), where n is the number of operators. If anyone have any ideas why the number of ways is always (2n)!/((n+1)!n!), appreciate for sharing the insights.

Here is an example about how do I mean different ways of parenthesizing, for example, the two different ways of parenthesizing both results in False.

1^((0|0)|1) 1^(0|(0|1))

thanks in advance, Lin

Answer 1

The number of ways to fully parenthesize an expression is given by the Catalan numbers. By far the easiest way to understand why this is the case is using the following formula for the Catalan numbers:

When there are 0 operators, there is only one way to fully parenthesize an expression: (x).

When we have an expression with n operators, we can place the first operator in n places:

x|x       One operator, one possible location.
 ^

x|x|x     Two operators, two possible locations.
 ^ ^

When we 'place' an operator, we simply multiply the possible number of ways to parenthesize the left-hand side by the number of ways to parenthesize the right-hand side. We do this for every possible location, and sum those possibilities.