numvana

Catalan Number Calculator

Compute the nth Catalan number exactly, a count that turns up in balanced-parentheses sequences, binary trees, polygon triangulations, and other combinatorics problems.

Catalan number C(n)
42
Central binomial coefficient C(2n, n)
252

How it works

The nth Catalan number has the closed form C(n) = C(2n, n) / (n + 1), where C(2n, n) is the central binomial coefficient "2n choose n." Rather than computing two large factorials directly, this calculator walks the equivalent term-by-term recurrence C(k+1) = C(k) × 2(2k+1) / (k+2), which stays an exact integer at every single step, then recovers C(2n, n) from the identity above.

Catalan numbers count a surprising number of unrelated-looking combinatorics problems that all turn out to be the same underlying structure: the number of ways to correctly match n pairs of parentheses, the number of distinct binary search trees on n nodes, the number of ways to triangulate a convex polygon with n + 2 sides, and the number of monotonic lattice paths from one corner of an n×n grid to the other that never cross the diagonal, among others.

FAQ

Why does n have a cap of 1000?

The recurrence itself is exact for any n, but Catalan numbers grow extremely fast — C(1000) already has well over 500 digits — so the cap keeps the computation and the displayed result at a reasonable size rather than a mathematical limitation.

What's a concrete example for a small n?

For n = 3, C(3) = 5. Those 5 are exactly the 5 ways to validly match 3 pairs of parentheses: ((())), (()()), (())(), ()(()), and ()()().

Related calculators