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.
How we build and check this calculator
This calculator runs entirely in your browser, so the numbers you enter stay on your device. The math behind it is written by hand and tested against worked examples and standard references before the page goes live.
SuperGlobalCalculator is independently built and maintained. See how we build and verify our calculators.