TOPICS
Search

Bracketing


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)),
(1)

the last five of which are binary.

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

 1/4(1+x-sqrt(1-6x+x^2))=x+x^2+3x^3+11x^4+45x^5
(2)

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

 s_n=(3(2n-3)s_(n-1)-(n-3)s_(n-2))/n
(3)

(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

S(n)=(3P_(n-1)(3)-P_(n-2)(3))/(4n)
(4)
=1/4[-P_n(3)+6P_(n-1)(3)-P_(n-2)(3)]
(5)

(Vardi 1991, p. 199).

The numbers are also given by

 s_n=sum_(i_1+...+i_k=n)s(i_1)...s(i_k)
(6)

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, Super Catalan Number

Explore with Wolfram|Alpha

References

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

Bracketing

Cite this as:

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

Subject classifications