Number Theory

Catalan Number Calculator | Sequence, Formula & Applications

Compute Catalan numbers Cₙ up to n = 30 using exact arithmetic. Shows the closed-form formula C(2n,n)/(n+1), the recursive formula, and a table of all values. Explains applications: number of valid bracket sequences, binary tree shapes, convex polygon triangulations, mountain ranges, and ballot paths.

Instant Results100% FreeAny DeviceNo Sign-up

PRESETS

Show table up to n =

Selected n (for recurrence & apps)

C₅

Ratio C₆/C₅ = 3.1429 (approaches 4 as n→∞)

Recurrence: C₅ = C0×C4 + C1×C3 + C2×C2 + C3×C1 + C4×C0

C0×C4 = 14C1×C3 = 5C2×C2 = 4C3×C1 = 5C4×C0 = 14

Sum = 42

APPLICATION EXPLORER

Valid bracket sequences of length 2×5: 42

C_n counts the number of ways to arrange n pairs of matching parentheses.

CATALAN NUMBER TABLE

n	Cₙ (exact)	Brackets (len 2n)	Trees (n+1 leaves)	Cₙ₊₁/Cₙ
0	1	1	1	1.0000
1	1	1	1	2.0000
2	2	2	2	2.5000
3	5	5	5	2.8000
4	14	14	14	3.0000
5	42	42	42	3.1428
6	132	132	132	3.2500
7	429	429	429	3.3333
8	1430	1430	1430	3.4000
9	4862	4862	4862	3.4545
10	16796	16796	16796	—

What Is the Catalan Number Calculator | Sequence, Formula & Applications?

Compute exact Catalan numbers up to n = 30 using BigInt arithmetic. Displays the full table with ratios converging to 4, the recurrence decomposition for any selected n, and an application explorer covering bracket sequences, binary trees, polygon triangulations, and Dyck paths.

Formula

Cₙ = C(2n,n)/(n+1) = (2n)!/(n!(n+1)!)   Recurrence: Cₙ = Σᵢ₌₀ⁿ⁻¹ Cᵢ × Cₙ₋₁₋ᵢ

How to Use

1
Use the "Show table up to n" slider to set the maximum n for the Catalan table (0 to 30).
2
Use the "Selected n" slider to choose which Catalan number to analyse in detail.
3
Click a preset button (n=5, n=10, n=15) to jump to commonly studied values.
4
Read the exact value Cₙ and the ratio Cₙ₊₁/Cₙ (converges to 4) in the highlighted result box.
5
Review the recurrence decomposition: Cₙ = Σ Cᵢ × Cₙ₋₁₋ᵢ with every term shown.
6
Click an Application tab (Brackets, Trees, Triangulations, Mountain Ranges, Ratio) to see how Cₙ applies.
7
Scroll the table to compare Cₙ values, bracket counts, tree counts, and convergence ratios for all n.

Adjust the max n slider to set the table size, then select a specific n to explore its recurrence and applications.

Example Calculation

C₅ = 42. Recurrence: C₅ = C₀C₄ + C₁C₃ + C₂C₂ + C₃C₁ + C₄C₀ = 1×14 + 1×5 + 2×2 + 5×1 + 14×1 = 14+5+4+5+14 = 42. This means there are 42 valid bracket sequences of length 10, 42 full binary trees with 6 leaves, and 42 triangulations of a convex heptagon.

Understanding Catalan Number | Sequence, Formula & Applications

Catalan Numbers C₀ – C₁₂ with Three Interpretations

n	Cₙ	Bracket sequences (len 2n)	Binary trees (n+1 leaves)	Triangulations of (n+2)-gon
0	1	1	1	1
1	1	1	1	1
2	2	2	2	2
3	5	5	5	5
4	14	14	14	14
5	42	42	42	42
6	132	132	132	132
7	429	429	429	429
8	1,430	1,430	1,430	1,430
9	4,862	4,862	4,862	4,862
10	16,796	16,796	16,796	16,796
11	58,786	58,786	58,786	58,786
12	208,012	208,012	208,012	208,012

Growth Comparison: Catalan vs Fibonacci vs Factorial

Catalan numbers grow as roughly 4ⁿ / (n^(3/2) √π), faster than Fibonacci (φⁿ/√5) but far slower than n! for large n.

n	Catalan Cₙ	Fibonacci Fₙ	n! (factorial)	2ⁿ (exponential)
1	1	1	1	2
3	5	2	6	8
5	42	5	120	32
7	429	13	5040	128
10	16,796	55	3,628,800	1,024
12	208,012	144	479,001,600	4,096
15	9,694,845	610	1.31×10¹²	32,768

Applications Reference

›Valid bracket sequences: Cₙ = number of ways to arrange n pairs of matching parentheses. For n=4: 14 valid sequences.
›Full binary trees: Cₙ = number of structurally distinct full binary trees with n internal nodes (or n+1 leaves).
›Polygon triangulation: Cₙ = number of ways to triangulate a convex (n+2)-gon into n triangles using non-crossing diagonals.
›Dyck paths (mountain ranges): Cₙ = number of monotonic lattice paths from (0,0) to (2n,0) that never go below the x-axis. Each path is a sequence of n up-steps and n down-steps.
›Stack-sortable permutations: Cₙ = number of permutations of {1,…,n} that can be sorted by a single stack (avoiding pattern 231).
›Plane trees: Cₙ = number of rooted plane trees with n+1 nodes.
›Non-crossing partitions: Cₙ = number of non-crossing partitions of {1,2,…,n}.
›Ballot problem connection: the probability that candidate A (with a votes) is strictly ahead throughout the count when B has b votes is (a−b)/(a+b) — related to Catalan reflection arguments.

Frequently Asked Questions

What are Catalan numbers?

Catalan numbers are a sequence of positive integers (1, 1, 2, 5, 14, 42, 132, …) that appear as the answer to over 200 distinct combinatorial problems. They are named after Eugène Catalan who studied them in 1838, though the sequence was known to Euler and Segner earlier.

How is the closed form C(2n,n)/(n+1) derived?

One derivation uses the ballot problem: Cₙ = C(2n,n) − C(2n,n−1) = C(2n,n)/(n+1). Alternatively, the generating function approach gives C(x) = (1 − √(1−4x)) / (2x), whose series coefficients are exactly C(2n,n)/(n+1). For large n, Stirling's approximation gives Cₙ ≈ 4ⁿ / (n^(3/2) √π).

Why does the ratio Cₙ₊₁/Cₙ approach 4?

From the asymptotic formula Cₙ ≈ 4ⁿ / (n^(3/2) √π), the ratio Cₙ₊₁/Cₙ ≈ 4 × (n/(n+1))^(3/2) → 4 as n → ∞. The exact value is Cₙ₊₁/Cₙ = 2(2n+1)/(n+2), which approaches 4.

Can Catalan numbers overflow standard integers?

Yes. C₁₅ ≈ 9.7 million, C₂₀ ≈ 6.6 billion (exceeds 32-bit int), and C₃₀ has 17 digits (exceeds 64-bit int). This calculator uses JavaScript BigInt for exact arithmetic up to n = 30, where C₃₀ = 5,909,761,445,129,385,600 (19 digits).

How are Catalan numbers related to Pascal's triangle?

Cₙ = C(2n,n) / (n+1), where C(2n,n) is the central binomial coefficient — the middle element of row 2n in Pascal's triangle. So every Catalan number can be read from Pascal's triangle by taking the central entry and dividing by n+1.

Related Calculators

Fibonacci Calculator | F(n), Sequence & Check

Find any Fibonacci number F(n) with exact BigInt arithmetic up to F(10000), generate sequences with golden ratio convergence, and check whether any integer is a Fibonacci number using the algebraic 5n²±4 perfect-square test.

Pascal's Triangle Calculator

Generate Pascal's triangle up to any row and expand (a + b)ⁿ using the binomial theorem. Shows all coefficients and the full polynomial expansion.

Combination Calculator | nCr & n Choose r

Calculate C(n,r) combinations without repetition, C̄(n,r) with repetition, P(n,r) permutations, and nʳ, all in one tool. Supports BigInt exact arithmetic for large n, step-by-step working, Pascal's triangle, combination listing, and session persistence.

Sequence Analyzer | Detect Pattern, nth Term & Generate Terms

Enter any numerical sequence and automatically detect whether it is arithmetic, geometric, quadratic, cubic, Fibonacci-type, or power-based. Finds the closed-form nth term formula, builds a complete difference table at every order, generates the next N terms, and computes partial sums.

Number Sequence Calculator

Find the nth term of arithmetic, geometric, and other common sequences.