Status: #good
Tags: #definition

valid parenthesizations

A valid parenthesization of $n$ letters is an assigning of $n-1$ left and right parenthesis around or between letters to denote the different ways you can multiply (viewing multiplication formally as a binary operation).

Examples

• n=1 $(xy)$
• n=2 $((xy)z);(x(yz))$
• n=3 $(((xy)z)t);(x(y(zt)));((x(yz))t);(x((yz)t));((xy)(zt))$

Properties

• number of valid parenthesization of n+1 letters is catalan