Catalan numbers

Parametric equations

The Catalan number $C_n=\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$ counts several structures: the valid matchings of $n$ pairs of parentheses, the lattice paths from $(0,0)$ to $(n,n)$ that do not cross the diagonal, the triangulations of a convex $(n+2)$-gon, and others. The figure switches among views of the same $C_n$.

Recurrence:

Interaction

• Dyck path / Parentheses / Triangulation: three views of the same $C_n$
• Order n: set the size of the object. When $n>6$, Triangulation samples instead of listing every polygon
• Next: show another object of the same order

What to notice

• Next changes which object is drawn. It does not change $C_n$.
• A Dyck path is the parenthesis word read as steps that stay on one side of the diagonal. The arcs in the parenthesis view are the matching pairs.
• A triangulation cuts a convex $(n+2)$-gon into triangles. Past $n=6$ that view is a sample, not every triangulation.

Related

• Pascal’s triangle
• Path counting
• Geometric significance of the binomial expansion

Further reading

• Catalan number (Wikipedia)