TOPICS

# Bracketing

Take itself to be a bracketing, then recursively define a bracketing as a sequence where and each is a bracketing. A bracketing can be represented as a parenthesized string of s, with parentheses removed from any single letter 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:

 (1)

the last five of which are binary.

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

 (2)

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

 (3)

(Comtet 1974), giving the sequence for 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 for is

 (4) (5)

(Vardi 1991, p. 199).

The numbers are also given by

 (6)

for (Stanley 1997).

The first Plutarch number is equal to (Stanley 1997), suggesting that Plutarch's problem of ten compound propositions is equivalent to the number of bracketings. In addition, Plutarch's second number is given by (Habsieger et al. 1998).

Binary Bracketing, Plutarch Numbers, Super Catalan Number

## Explore with Wolfram|Alpha

More things to try:

## 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.

Bracketing

## Cite this as:

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