Take x itself to be a bracketing, then recursively define a bracketing as a sequence B=(B_1,...,B_k) where k>=2 and each B_i is a bracketing. A bracketing can be represented as a parenthesized string of xs, with parentheses removed from any single letter x for clarity of notation (Stanley 1997). Bracketings built up of binary operations only are called binary bracketings. For example, four letters have 11 possible bracketings:

 xxxx (xx)xx x(xx)x xx(xx); (xxx)x x(xxx) ((xx)x)x (x(xx))x; (xx)(xx) x((xx)x) x(x(xx)),

the last five of which are binary.

The number of bracketings on n letters is given by the generating function


(Schröder 1870, Stanley 1997) and the recurrence relation


(Comtet 1974), giving the sequence for s_n as 1, 1, 3, 11, 45, 197, 903, ... (OEIS A001003). They are therefore equivalent to the super Catalan numbers.

A closed form expression in terms of Legendre polynomials P_n(x) for n>1 is


(Vardi 1991, p. 199).

The numbers are also given by


for n>=2 (Stanley 1997).

The first Plutarch number 103049 is equal to s_(10) (Stanley 1997), suggesting that Plutarch's problem of ten compound propositions is equivalent to the number of bracketings. In addition, Plutarch's second number 310954 is given by (s_(10)+s_(11))/2=310954 (Habsieger et al. 1998).

See also

Binary Bracketing, Plutarch Numbers, Root Bracketing, Super Catalan Number

Explore with Wolfram|Alpha


Comtet, L. "Bracketing Problems." §1.15 in Advanced Combinatorics: The Art of Finite and Infinite Expansions, rev. enl. ed. Dordrecht, Netherlands: Reidel, pp. 52-57, 1974.Habsieger, L.; Kazarian, M.; and Lando, S. "On the Second Number of Plutarch." Amer. Math. Monthly 105, 446, 1998.Schröder, E. "Vier combinatorische Probleme." Z. Math. Physik 15, 361-376, 1870.Sloane, N. J. A. Sequence A001003/M2898 in "The On-Line Encyclopedia of Integer Sequences."Stanley, R. P. "Hipparchus, Plutarch, Schröder, and Hough." Amer. Math. Monthly 104, 344-350, 1997.Vardi, I. Computational Recreations in Mathematica. Reading, MA: Addison-Wesley, pp. 198-199, 1991.

Referenced on Wolfram|Alpha


Cite this as:

Weisstein, Eric W. "Bracketing." From MathWorld--A Wolfram Web Resource.

Subject classifications