Binary Bracketing

A binary bracketing is a Bracketing built up entirely of binary operations. The number of binary bracketings of $n$ letters (Catalan's Problem) are given by the Catalan Numbers $C_{n-1}$, where

$$C_n \equiv {1\over n+1}{2n\choose n} = {1\over n+1}{(2n)!\over n!^2}={(2n)!\over (n+1)!n!},$$

where ${2n\choose n}$ denotes a Binomial Coefficient and $n!$ is the usual Factorial, as first shown by Catalan in 1838. For example, for the four letters $a$, $b$, $c$, and $d$ there are five possibilities: $((ab)c)d$, $(a(bc))d$, $(ab)(cd)$, $a((bc)d)$, and $a(b(cd))$, written in shorthand as $((xx)x)x$, $(x(xx))x$, $(xx)(xx)$, $x((xx)x)$, and $x(x(xx))$.

See also Bracketing, Catalan Number, Catalan's Problem

References

Schröder, E. ``Vier combinatorische Probleme.'' Z. Math. Physik 15, 361-376, 1870.

Sloane, N. J. A. Sequence A000108/M1459 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and extended entry in Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.

Stanley, R. P. ``Hipparchus, Plutarch, Schröder, and Hough.'' Amer. Math. Monthly 104, 344-350, 1997.