42
252
12
132
3.142857
44.79
42
252
12
132
3.142857
44.79
The Catalan Number Calculator computes the $$n$$-th Catalan number $$C_n$$, one of the most ubiquitous sequences in combinatorics. Catalan numbers are defined by the closed-form formula:
$$C_n = \frac{1}{n+1}\binom{2n}{n} = \frac{(2n)!}{(n+1)! \cdot n!}$$
The sequence begins: $$1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, \ldots$$ and grows approximately as $$C_n \sim \frac{4^n}{n^{3/2}\sqrt{\pi}}$$.
Named after the Belgian mathematician Eugène Charles Catalan (1814–1894), these numbers were actually discovered earlier by Euler in the context of polygon triangulation and by Leonhard Euler and Johann Andreas von Segner in the 18th century. The sequence appears in the On-Line Encyclopedia of Integer Sequences as A000108 and has been called "the most frequently encountered sequence in mathematics" by combinatorialist Richard Stanley, who compiled over 200 distinct combinatorial interpretations.
Catalan numbers count an extraordinary variety of structures. $$C_n$$ equals the number of valid parenthesizations with $$n$$ pairs of parentheses, the number of full binary trees with $$n+1$$ leaves, the number of triangulations of a convex $$(n+2)$$-gon, the number of Dyck paths from $$(0,0)$$ to $$(2n,0)$$ that never dip below the $$x$$-axis, the number of monotonic lattice paths in an $$n \times n$$ grid that stay below the diagonal, and the number of non-crossing partitions of $$\{1, \ldots, n\}$$.
The recurrence relation $$C_0 = 1$$, $$C_{n+1} = \sum_{i=0}^{n} C_i C_{n-i}$$ reflects the recursive decomposition of these structures. For binary trees, the left subtree has $$i$$ internal nodes and the right has $$n - i$$, giving the convolution. The generating function $$C(x) = \frac{1 - \sqrt{1 - 4x}}{2x}$$ satisfies $$C(x) = 1 + x C(x)^2$$.
In computer science, Catalan numbers appear in the analysis of stack-sortable permutations, the counting of binary search trees, and the complexity of matrix chain multiplication. In computational biology, they count RNA secondary structures. This calculator uses Stirling's approximation for the factorials to compute Catalan numbers for moderate values of $$n$$.
The calculator computes Catalan numbers using the binomial coefficient formula with Stirling's approximation for log-factorials.
Step 1: Compute $$\ln\binom{2n}{n}$$. Using Stirling's approximation $$\ln(k!) \approx k\ln k - k + \frac{1}{2}\ln(2\pi/k)$$:
$$\ln\binom{2n}{n} = \ln(2n)! - 2\ln(n!) \approx 2n\ln(2n) - 2n\ln(n) + \text{correction terms}$$
Step 2: Compute $$C_n$$.
$$C_n = \frac{1}{n+1}\binom{2n}{n} = \frac{1}{n+1} \exp\left(\ln\binom{2n}{n}\right)$$
Step 3: Compute neighbors. $$C_{n-1}$$ and $$C_{n+1}$$ are computed similarly. The ratio $$C_{n+1}/C_n = \frac{2(2n+1)}{n+2}$$ approaches 4 as $$n \to \infty$$.
Step 4: Asymptotic approximation.
$$C_n \sim \frac{4^n}{n^{3/2}\sqrt{\pi}}$$
This approximation improves with increasing $$n$$ and captures the exponential growth rate of 4.
Cₙ is the $$n$$-th Catalan number. For combinatorial applications, this counts the number of valid structures of size $$n$$ (parenthesizations, binary trees, Dyck paths, etc.).
Cₙ₋₁ and Cₙ₊₁ provide context for the growth rate. The ratio $$C_{n+1}/C_n$$ approaches 4 as $$n$$ increases.
Cₙ₊₁/Cₙ shows the growth factor. The exact ratio is $$\frac{2(2n+1)}{n+2}$$, which starts at 2 for $$n=0$$ and monotonically increases toward 4.
Asymptotic approximation $$4^n/(n^{3/2}\sqrt{\pi})$$ gives the leading-order behavior. The relative error decreases as $$O(1/n)$$.
C(2n, n) is the central binomial coefficient, from which the Catalan number is derived by dividing by $$n+1$$.
Inputs
Results
C₅ = C(10,5)/6 = 252/6 = 42. There are 42 ways to arrange 5 pairs of parentheses, 42 binary trees with 6 leaves, and 42 triangulations of a heptagon. The asymptotic value 46.21 overestimates by about 10%.
Inputs
Results
C₁₀ = C(20,10)/11 = 184756/11 = 16796. The ratio C₁₁/C₁₀ ≈ 3.50, approaching the asymptotic limit of 4. The asymptotic formula gives 18725, within 11.5% of the exact value.
Catalan numbers count over 200 combinatorial structures. The most common include: valid sequences of $$n$$ pairs of matched parentheses, rooted binary trees with $$n+1$$ leaves, triangulations of a convex $$(n+2)$$-gon, Dyck paths of length $$2n$$, monotonic lattice paths below the diagonal, non-crossing partitions, and stack-sortable permutations of length $$n$$.
The central binomial coefficient $$\binom{2n}{n}$$ counts all lattice paths from $$(0,0)$$ to $$(n,n)$$ and grows as $$4^n/(\sqrt{\pi n})$$. The Catalan number divides by $$n+1$$ to count only the paths that stay below the diagonal (the ballot problem constraint), giving the additional $$1/n^{3/2}$$ decay factor. The base 4 comes from $$\binom{2n}{n} \approx 4^n$$.
A Dyck path is a lattice path from $$(0,0)$$ to $$(2n,0)$$ using steps $$(1,1)$$ (up) and $$(1,-1)$$ (down) that never goes below the $$x$$-axis. Each up step corresponds to an opening parenthesis and each down step to a closing parenthesis. The constraint of non-negativity ensures valid nesting. The number of Dyck paths of length $$2n$$ is exactly $$C_n$$.
$$C_n$$ counts the number of distinct full binary trees (every node has 0 or 2 children) with $$n+1$$ leaves. The recursive structure mirrors the Catalan recurrence: the root splits the tree into a left subtree with $$i$$ internal nodes and a right subtree with $$n-1-i$$ internal nodes, giving $$C_{n} = \sum C_i C_{n-1-i}$$.
The ordinary generating function is $$C(x) = \sum_{n=0}^{\infty} C_n x^n = \frac{1 - \sqrt{1 - 4x}}{2x}$$. It satisfies the functional equation $$C(x) = 1 + xC(x)^2$$, reflecting the recursive decomposition. The radius of convergence is $$1/4$$, consistent with the $$4^n$$ growth rate.
Stirling's approximation $$\ln(n!) \approx n\ln n - n + \frac{1}{2}\ln(2\pi/n)$$ is highly accurate for $$n \geq 5$$. The relative error is roughly $$1/(12n)$$. For Catalan numbers with $$n \leq 20$$, the approximation combined with rounding gives exact integer results. For $$n > 25$$, floating-point precision may introduce small errors.
Roboculator Team
The Roboculator Team explains calculations, planning tools, and practical formulas in clear language for real-life situations.
How helpful was this calculator?
Be the first to rate!
