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)
|
 |  | ![1/4[-P_n(3)+6P_(n-1)(3)-P_(n-2)(3)]](/images/equations/Bracketing/Inline16.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. In addition,
Plutarch's second number 
is given by 
(Habsieger et al. 1998).
