Bracketing

Take $x$ itself to be a bracketing, then recursively define a bracketing as a sequence $B=(B_1,\ldots,B_k)$ where $k\geq 2$ and each $B_i$ is a bracketing. A bracketing can be represented as a parenthesized string of $x$s, 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:

$$\matrix{ xxxx & (xx)xx & x(xx)x & xx(xx)\cr (xxx)x & x(xxx) & ((xx)x)x & (x(xx))x\cr (xx)(xx) & x((xx)x) & x(x(xx)),\cr}$$

the last five of which are binary.

The number of bracketings on $n$ letters is given by the Generating Function

$${\textstyle{1\over 4}}(1+x-\sqrt{1-6x+x^2}\,)=x+x^2+3x^3+11x^4+45x^5$$

(Schröder 1870, Stanley 1997) and the Recurrence Relation

$$s_n={3(2n-3)s_{n-1}-(n-3)s_{n-2}\over n}$$

(Sloane), giving the sequence for $s_n$ as 1, 1, 3, 11, 45, 197, 903, ... (Sloane's A001003). The numbers are also given by

$$s_n=\sum_{i_1+\ldots+i_k=n}s(i_1)\cdots s(i_k)$$

for $n\geq 2$ (Stanley 1997).

The first Plutarch Number 103,049 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 310,954 is given by $(s_{10}+s_{11})/2=310,954$ (Habsieger et al. 1998).

See also Binary Bracketing, Plutarch Numbers

References

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 ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.

Stanley, R. P. ``Hipparchus, Plutarch, Schröder, and Hough.'' Amer. Math. Monthly 104, 344-350, 1997.