A bracketing is either a single letter 
or an ordered 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. The outermost parentheses are omitted in the following examples.
Four letters have 11 possible bracketings:
 |
(1)
|
the last five of which are binary.
Let 
be the number of bracketings on 
letters, where 
is a positive integer.
Its generating function is
 |
(2)
|
(Schröder 1870, Stanley 1997). The recurrence relation is
 |
(3)
|
for 
, with 
(Comtet 1974, Stanley 1997). The sequence
for 
, 2, ... is 1, 1, 3, 11, 45, 197, 903,
... (OEIS A001003). These are the super
Catalan numbers, with 
corresponding to OEIS A001003 at index 
.
A closed-form expression in terms of Legendre polynomials 
for 
is
 |  |  |
(4)
|
 |  | ![1/4[-P_n(3)+6P_(n-1)(3)-P_(n-2)(3)]](/images/equations/Bracketing/Inline22.svg) |
(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. Plutarch's
reported second number is 310,952 (Stanley 1997). Habsieger et al. (1998)
proposed the nearby value 
(Pergola and Sulanke 1998).
