TOPICS
Search

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=1/(n+1)(2n; n)
(1)
=1/(n+1)((2n)!)/(n!^2)=((2n)!)/((n+1)!n!),
(2)

where (2n; 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

Explore with Wolfram|Alpha

References

Schröder, E. "Vier combinatorische Probleme." Z. Math. Physik 15, 361-376, 1870.Sloane, N. J. A. Sequence A000108/M1459 in "The On-Line Encyclopedia of Integer Sequences."Sloane, N. J. A. and Plouffe, S. Figure M1459 in 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.

Referenced on Wolfram|Alpha

Binary Bracketing

Cite this as:

Weisstein, Eric W. "Binary Bracketing." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/BinaryBracketing.html

Subject classifications