Catalan Numbers

Combinatorics · Axiom Academy

Discover one of combinatorics' most elegant sequences through balanced parentheses, binary trees, and polygon triangulations 1. Definition and Recurrence Relation The n -th Catalan number C n satisfies a beautiful recurrence relation that captures how larger structures are built from smaller ones. The recurrence says: to count structures of size n , sum over all ways to split into a left part of size i and right part of size n-1-i . While the recurrence is intuitive, we can derive an explicit formula for C n using generating functions or direct counting arguments. The formula involves binomial coefficients, reflecting the connection to lattice path counting. 3. Interpretation: Balanced Parentheses C n counts the number of valid ways to arrange n pairs of balanced parentheses. Count: C 3 = 5 valid sequences Each valid sequence has the property that every prefix has at least as many open parentheses as closed ones. 4. Interpretation: Full Binary Trees C n also counts the number of full binary trees with n+1 leaves (or equivalently, n internal nodes). The recurrence relation corresponds to choosing how to split the tree at the root: the left subtree can have 0 to n-1 internal nodes, and the right subtree has the remaining nodes. There are C 3 = 5 distinct tree shapes, each with 4 leaves. 5. Interpretation: Polygon Triangulations C n counts the number of ways to triangulate a convex polygon with n+2 vertices using non-crossing diagonals.

This is the written version of the interactive lesson above. See the full Combinatorics course.