Equivalence of Three Catalan Number Interpretations
Equivalence of Three Catalan Number Interpretations
The Catalan numbers count:
• the ways a polygon with sides can be cut into triangles;
n+2
n
• the ways to parenthesize a sequence of factors to be multiplied, two at a time;
n+1
• the planted trivalent trees with leaves.
n+1
This Demonstration shows the equivalence of the three interpretations by optionally labeling each polygon triangulation with the corresponding parenthesized expression, tree, or both.