About

Catalan numbers form a sequence of natural integers that appear across discrete mathematics: counting valid parenthesizations, binary tree structures, polygon triangulations, lattice paths below the diagonal, and non-crossing partition counts. The n-th Catalan number C_n grows asymptotically as 4ⁿn^3/2 √π, which means manual computation becomes impractical past C₂₀. Incorrect sequence values propagate errors in algorithm analysis, dynamic programming table sizing, and combinatorial proof verification. This generator computes exact arbitrary-precision Catalan numbers using BigInt arithmetic through the iterative recurrence C_n = C_n−1 × 2(2n − 1) ÷ (n + 1), avoiding factorial overflow entirely.

The tool supports indices from 0 to 500. Note: C₅₀₀ has 299 decimal digits. Results are exact, not floating-point approximations. For research use, be aware that OEIS designates this as sequence A000108.

Formulas

The n-th Catalan number is defined by the closed-form binomial expression:

C_n = 1n + 1 ⋅ (2n)!n! ⋅ n!

This tool avoids computing large factorials directly. Instead, it uses the iterative recurrence relation which is numerically stable with integer arithmetic:

C₀ = 1 , C_n = C_n−1 ⋅ 2(2n − 1)n + 1

The asymptotic growth approximation for large n is given by:

C_n ∼ 4ⁿn^3/2 √π

The generating function for the sequence satisfies the quadratic equation:

C(x) = 1 − √1 − 4x2x

Where C_n = the n-th Catalan number (dimensionless integer), n = non-negative index (n ∈ N₀), and n! = factorial of n.

Reference Data

n	C_n	Digit Count	Combinatorial Interpretation
0	1	1	Empty structure (base case)
1	1	1	Single valid pair of parentheses: `()`
2	2	1	Binary trees with 2 nodes
3	5	1	Triangulations of a pentagon
4	14	2	Non-crossing partitions of {1,2,3,4}
5	42	2	Dyck paths of length 10
6	132	3	Full binary trees with 7 leaves
7	429	3	Stack-sortable permutations of length 7
8	1,430	4	Monotone lattice paths in 8×8 grid
9	4,862	4	Ways to connect 2×9 points on circle without crossings
10	16,796	5	Valid sequences of 10 pairs of parentheses
15	9,694,845	7	Polygon triangulations of 17-gon
20	6,564,120,420	10	Exceeds 32-bit integer range
25	4,861,946,401,452	13	Ballot problem configurations
30	5,909,761,445,129,385,600	19	Exceeds 64-bit float precision
50	1.978 × 10²⁸	29	RNA secondary structure folds
100	8.969 × 10⁵⁸	59	Planar graph enumeration
200	2.232 × 10¹¹⁸	119	Requires arbitrary-precision arithmetic
500	5.395 × 10²⁹⁸	299	Maximum index supported by this tool

Frequently Asked Questions

JavaScript's Number type uses IEEE 754 double-precision floating point, which provides exact integer representation only up to 2⁵³ − 1 (approximately 9 × 10¹⁵). The Catalan number C₃₀ = 5,909,761,445,129,385,600 already approaches this boundary. By C₃₅, standard arithmetic produces rounding errors. BigInt provides arbitrary-precision integer arithmetic, ensuring every digit of C₅₀₀ (a 299-digit number) is exact.

The direct formula C(n) = (2n)! / ((n+1)! × n!) requires computing factorials that grow super-exponentially. For n = 100, (200)! has 375 digits. The recurrence C(n) = C(n−1) × 2(2n−1) / (n+1) multiplies and divides by small values at each step, keeping intermediate results close in magnitude to the final answer. The division is always exact because of the algebraic structure of Catalan numbers - 2(2n−1) is always divisible by (n+1) when applied to C(n−1).

C(n) counts at least 66 distinct combinatorial objects (Richard Stanley's catalog). Key examples: valid arrangements of n pairs of parentheses, full binary trees with n+1 leaves, monotone lattice paths from (0,0) to (n,n) that never cross the diagonal, triangulations of an (n+2)-gon, non-crossing partitions of an n-element set, and 321-avoiding permutations of length n. The OEIS entry A000108 provides the comprehensive list.

C(n) is odd if and only if n = 2ᵏ − 1 for some non-negative integer k (i.e., n = 0, 1, 3, 7, 15, 31, 63, …). For all other indices, C(n) is even. This result follows from Kummer's theorem applied to the central binomial coefficient. Additionally, C(p) ≡ 2 (mod p) for any prime p, which connects Catalan numbers to modular arithmetic and Wolstenholme's theorem.

The approximation C(n) ~ 4ⁿ / (n^(3/2) × √π) converges slowly. At n = 10, the relative error is approximately 4.5%. At n = 100, it drops to about 0.4%. At n = 500, the error is roughly 0.08%. For precise computation, always use the exact recurrence. The asymptotic form is useful for estimating digit counts and growth rates, not for obtaining actual values.

Yes. For C(n) mod p, use Lucas' theorem combined with modular inverse. Compute the binomial coefficient C(2n, n) mod p using iterative multiplication with Fermat's little theorem for division (since p is prime, a⁻¹ ≡ a^(p−2) mod p). Then divide by (n+1) mod p. This tool computes exact BigInt values; for modular results, take the output mod your desired prime.