= 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 \b[$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.<Bijective Proof Problems by Richard P. Stanley>[§5, Problem 154, printed p. 38: binary parenthesizations of n+1 letters]{ref}
Back to article page
