Catalan Number Calculator
Compute the nth Catalan number C(n) used in combinatorics for counting binary trees, balanced parentheses, polygon triangulations, and lattice paths.
Catalan Numbers
The Catalan numbers form a sequence of integers that appear throughout combinatorics, computer science, and discrete mathematics. The first few values are 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, …
Formula
C(n) = (2n)! / ((n + 1)! × n!) = C(2n, n) / (n + 1)
Equivalent recurrence:
C(n+1) = ((4n + 2) × C(n)) / (n + 2)
with C(0) = 1.
Worked Example — n = 4
C(4) = 8! / (5! × 4!) = 40320 / (120 × 24) = 40320 / 2880 = 14
So there are 14 distinct binary trees with 4 nodes, 14 ways to pair 8 parentheses correctly, and 14 lattice paths in a 4×4 grid that never cross the diagonal.
Things Catalan Numbers Count
| C(n) counts | Example for n = 3 |
|---|---|
| Balanced bracket strings of length 2n | ((())), (()()), (())(), ()(()), ()()() = 5 |
| Binary trees with n internal nodes | 5 distinct trees |
| Triangulations of an (n+2)-gon | 5 ways to triangulate a pentagon |
| Mountain ranges with n up-steps and n down-steps | 5 patterns |
| Non-crossing partitions of n points on a circle | 5 partitions |
| Dyck paths from (0,0) to (2n,0) | 5 paths |
Growth Rate
Catalan numbers grow rapidly — roughly 4ⁿ / (n^(3/2) × √π) for large n. By n = 30 they exceed 3.8 billion. By n = 50 they exceed JavaScript’s safe integer range — use BigInt for exact answers beyond about n = 33.
Why So Universal?
Many combinatorial structures share an identical recursive decomposition: split into a left part, a chosen “root” element, and a right part — both sub-parts independently following the same rule. This recursion is precisely what generates the Catalan recurrence, which is why a single sequence counts so many seemingly different objects.
Applications
Compiler parsing, expression tree counting, RNA secondary structure prediction, and analysis of stack-based algorithms all rely on Catalan numbers.