Mathematics · Number Theory
Catalan Number Calculator
Computes the nth Catalan number using the closed-form binomial formula, with applications in combinatorics and recursive structure counting.
Calculator
Formula
C_n is the nth Catalan number (0-indexed). n is a non-negative integer. The binomial coefficient \binom{2n}{n} counts the number of ways to choose n items from 2n, and dividing by (n+1) corrects for invalid sequences. The factorial form (2n)! / ((n+1)! * n!) is equivalent and computationally direct.
Source: Stanley, R. P. (2015). Catalan Numbers. Cambridge University Press. Also: OEIS A000108.
How it works
Catalan numbers form a sequence C₀, C₁, C₂, … defined for all non-negative integers. The first several values are 1, 1, 2, 5, 14, 42, 132, 429, 1430, and 4862 — each term countable in dozens of distinct combinatorial interpretations. The sequence was popularized by the Belgian mathematician Eugène Charles Catalan in the 19th century, though earlier references appear in the work of Euler and Segner on polygon triangulation.
The closed-form formula is C_n = (1/(n+1)) × C(2n, n) = (2n)! / ((n+1)! × n!), where C(2n, n) is the central binomial coefficient. An equivalent recurrence relation is C_{n+1} = sum_{i=0}^{n} C_i × C_{n−i}, which expresses the (n+1)th Catalan number as a convolution of all previous ones. Asymptotically, C_n grows like 4^n / (n^{3/2} × sqrt(π)), meaning consecutive Catalan numbers eventually approach a ratio near 4 as n increases — a pattern visible in the Growth Ratio output above.
Applications of Catalan numbers appear across mathematics and computer science. They count: the number of ways to fully parenthesize n+1 factors (associativity orderings), the number of distinct binary trees with n+1 leaves, the number of monotonic lattice paths from (0,0) to (n,n) that stay on or below the diagonal (Dyck paths), the number of triangulations of a convex polygon with n+2 vertices, the number of non-crossing partitions of {1,…,n}, and the number of stack-sortable permutations of n elements. This remarkable universality makes them an essential tool in discrete mathematics and algorithm design.
Worked example
Suppose you want to find C₅, the 5th Catalan number (0-indexed), to determine how many distinct ways a convex heptagon (7-sided polygon) can be triangulated.
Step 1 — Identify n. For a convex polygon with n+2 sides, set n+2 = 7, so n = 5.
Step 2 — Compute the factorial terms.
(2×5)! = 10! = 3,628,800
(5+1)! = 6! = 720
5! = 120
Step 3 — Apply the formula.
C₅ = 3,628,800 / (720 × 120) = 3,628,800 / 86,400 = 42
Result: A convex heptagon can be triangulated in exactly 42 distinct ways. This matches the known sequence value C₅ = 42 (OEIS A000108).
Ratio check: C₅ / C₄ = 42 / 14 = 3.0000, consistent with the ratio formula 2(2n−1)/(n+1) = 2×9/6 = 3.
Limitations & notes
This calculator supports indices from n = 0 to n = 18 using exact integer arithmetic with JavaScript's 64-bit floating-point representation. Beyond n = 18, the factorial values exceed safe integer precision (2^53 − 1 ≈ 9 × 10¹⁵), and results will lose accuracy or overflow. For large n (up to hundreds or thousands), use arbitrary-precision libraries such as Python's math.factorial, Mathematica's CatalanNumber[], or big-integer implementations. The recurrence relation is also numerically stable for large n in arbitrary precision arithmetic. Note that n must be a non-negative integer; the formula is undefined for negative or fractional inputs. The asymptotic formula C_n ≈ 4^n / (n^{3/2} √π) is useful for very large n estimates but does not give exact integer values.
Frequently asked questions
What is the 0th Catalan number?
C₀ = 1 by definition. Applying the formula: (2×0)! / ((0+1)! × 0!) = 1 / (1 × 1) = 1. This base case is consistent with the recurrence, where C₀ = 1 represents the empty structure (one way to do nothing).
How fast do Catalan numbers grow?
Catalan numbers grow exponentially. Asymptotically, C_n ≈ 4^n / (n^{3/2} √π). This means each successive Catalan number is roughly 4 times the previous one for large n. For example, C₁₀ = 16,796 and C₁₅ = 9,694,845 — an increase of over 500× in just 5 steps.
What are the first ten Catalan numbers?
The first ten Catalan numbers (C₀ through C₉) are: 1, 1, 2, 5, 14, 42, 132, 429, 1430, and 4862. These are listed in OEIS sequence A000108 and appear in dozens of independent combinatorial counting problems.
How are Catalan numbers related to binary trees?
C_n counts the number of structurally distinct full binary trees with n+1 leaves, or equivalently, the number of ordered binary trees with n internal nodes. For n = 3, C₃ = 5, meaning there are exactly 5 different shapes of full binary tree with 4 leaves — a classic result used in algorithm analysis and expression tree enumeration.
Can Catalan numbers be computed using Pascal's triangle?
Yes. The central binomial coefficient C(2n, n) appears on the center column of Pascal's triangle. Dividing each central entry by (n+1) gives the corresponding Catalan number. For example, the 10th row center entry is C(10,5) = 252, and C₅ = 252 / 6 = 42. This geometric connection makes Catalan numbers directly readable from Pascal's triangle with a simple division.
Last updated: 2025-01-15 · Formula verified against primary sources.