 Binary parenthesization

A binary parenthesization specifies the order of binary operations on a fixed ordered list of operands, combining exactly two existing expressions at each step. It has a full binary tree as its expression structure: operands are leaves and operations are internal vertices. For four operands $a,b,c,d$, the five possibilities are $((ab)c)d$, $(a(bc))d$, $(ab)(cd)$, $a((bc)d)$, and $a(b(cd))$.

A binary parenthesization of $n+1$ operands contains $n$ binary operations. At the last operation, its left expression can contain $k$ operations and its right expression $n-1-k$. The Catalan recurrence therefore gives $C_n$ possible evaluation structures. The order of operands stays fixed; this is not a count of their permutations. Even for an associative operation whose result is unchanged, different structures can have different evaluation costs, as in the matrix-chain multiplication problem.^[ref]