Bracketings

Bracketings are the distinct ways to place parentheses in a product or expression to specify the order of evaluation when the operation is not assumed to be associative. Given n factors x1, x2, ..., xn and a binary operation, a bracketing is a fully parenthesized form of the expression. Each bracketing corresponds to a full binary tree with n leaves, and thus to a particular parsing or evaluation order.

The number of bracketings of n factors is the Catalan number C_{n-1}. For n = 2 there is 1 bracketing: (x1 x2); for n = 3 there are 2: (x1 (x2 x3)) and ((x1 x2) x3); for n = 4 there are 5, and so on. The Catalan numbers are given by C_m = (1/(m+1)) * binomial(2m, m). Equivalently, for n factors the count is C_{n-1} = (1/n) * binomial(2n-2, n-1).

A standard recurrence is B(1) = 1 and B(n) = sum_{i=1}^{n-1} B(i) * B(n-i) for n > 1, reflecting the choice of a top-level split into left and right subexpressions. Bracketings have interpretations beyond arithmetic: they correspond to plane binary trees and to Dyck paths, and they appear in combinatorics, linguistics, and the study of non-associative algebraic structures. In contexts where the operation is associative, different bracketings evaluate to the same result, but bracketings remain a useful concept for understanding structure, parsing, and counting in non-associative settings.