Catalan Number Calculator (Cₙ)
Catalan numbers Cₙ = (1/(n+1))·C(2n, n) = (2n)! / ((n+1)!·n!) appear more often in enumerative combinatorics than almost any other sequence. The very same value Cₙ counts balanced parenthesis strings on n pairs, full ordered binary trees with n leaves, monotonic lattice paths from (0,0) to (n,n) that stay on or above the diagonal, triangulations of a convex (n+2)-gon, stack-sortable permutations, non-crossing perfect matchings on 2n points on a circle — at least a few dozen distinct combinatorial families collapse to this one count. Enter n (0–1000) and the tool returns the exact value via BigInt, plus four of those interpretations and the full C₀–C₂₀ table for reference.
Enter an integer n between 0 and 1000.
Catalan number Cₙ
132
Sequence
C₀ through C₂₀ for quick reference (max 21 shown).
What C{n} counts (four equivalent objects)
- ·—
- ·—
- ·—
- ·—
References: OEIS A000108; Stanley, Enumerative Combinatorics, §6.2.
Formula
Cₙ = (1 / (n + 1)) · C(2n, n) = (2n)! / ((n + 1)! · n!) Recurrence: Cₙ₊₁ = Cₙ · 2(2n + 1) / (n + 2) Convolution: Cₙ₊₁ = Σ_{i=0..n} Cᵢ · Cₙ₋ᵢ Asymptotic: Cₙ ~ 4ⁿ / (n^(3/2) · √π)
- · First 11 values: 1, 1, 2, 5, 14, 42, 132, 429, 1 430, 4 862, 16 796. OEIS A000108 lists the canonical references and many more identities.
- · Catalan numbers grow fast: Cₙ ~ 4ⁿ / (n^{3/2}·√π). C₃₀ already exceeds 3.8 × 10¹⁵; C₁₀₀₀ has 598 decimal digits — hence BigInt arithmetic, sidestepping the 2⁵³ limit of JavaScript Number.
- · The textbook interview problem "how many valid arrangements of n pairs of parentheses?" is exactly Cₙ. Standard solutions use O(n²) DP; this tool uses the O(n) multiplicative form binomial(2n, n) / (n + 1).
- · Dyck-path picture: sequences of +1 / −1 steps of length 2n that start and end at 0 with every partial sum ≥ 0 — equivalent to counting random walks on stock prices that never dip below the open.
- · Triangulations of a convex (n+2)-gon by non-crossing diagonals into n triangles is also Cₙ. Euler noticed this in 1751, and the count is what Eugène Catalan studied in 1838.
- · Relation to central binomial coefficient: Cₙ = C(2n,n) − C(2n,n−1) = C(2n,n) / (n + 1). The "reflection principle" gives the slickest proof, also relating to the classical Bertrand ballot problem.
- · Sources: OEIS A000108; Richard Stanley, Enumerative Combinatorics Vol. 2, §6.2 (the "Catalan numbers exercises" enumerate 207 distinct interpretations); Eugène Catalan (1838).
Frequently asked
Why do so many different combinatorial problems all give the same sequence?
Because they are all isomorphic under relabelling — you can always map one to another preserving the same recursive structure. The common parent picture is the Dyck path (n up-steps and n down-steps that never go below zero): (1) replace "up" with "(" and "down" with ")" → balanced parentheses; (2) replace "up" with right and "down" with up → monotonic lattice paths above the diagonal; (3) split a path at its first return to zero → full binary tree recursion; (4) fix an edge of a convex polygon and choose the triangle containing it → polygon triangulation. Once you spot the recurrence Cₙ₊₁ = Σ Cᵢ · Cₙ₋ᵢ in any problem, the answer is almost certainly a Catalan number. Stanley's Enumerative Combinatorics §6.2 enumerates 207 bijectively equivalent "Catalan structures".
How are Catalan numbers related to the binomial coefficient C(2n, n)?
Direct identity: Cₙ = C(2n, n) / (n + 1) = C(2n, n) − C(2n, n − 1). Intuitively C(2n, n) counts all 2n-step paths with n up and n down moves (regardless of whether they dip below zero), while Cₙ only counts paths that stay non-negative. The famous reflection principle shows that paths that cross the boundary are in bijection with all paths from (0, −1) to (n, n), of which there are C(2n, n − 1). So the allowed count is C(2n, n) − C(2n, n − 1), which algebraically simplifies to C(2n, n) / (n + 1). This tool uses the O(n) form — even n = 1000 returns instantly.
What happens if I want n larger than 1000?
The tool caps n at 1000 for UI responsiveness — even n = 1000 yields a 598-digit value, and the result quickly stops being useful as a literal number beyond that. If you really need larger Cₙ, use `math.comb(2*n, n) // (n + 1)` in Python, mpmath's `bin`, or any arbitrary-precision library. Asymptotically Cₙ ~ 4ⁿ / (n^{3/2}·√π), so C(10⁴) is about 6 014 digits and C(10⁶) is about 600 000 digits — squarely in symbolic-math territory. Day-to-day algorithmic and contest problems essentially stay within n ≤ 100.
Related tools
Percentage Calculator
Percent of, percent change, and percent add/subtract in one.
GCD & LCM Calculator
Enter 2–6 positive integers to get the greatest common divisor (HCF / GCD) and least common multiple (LCM), with the Euclidean step chain shown.
Average Calculator (Mean / Median / Mode)
Enter a list of numbers to get the mean, median, mode, range plus standard deviation, variance and total.
Quadratic Equation Solver
Enter the coefficients of ax² + bx + c = 0 to find the real or complex roots, discriminant and vertex.
Password Strength (Entropy) Calculator
Estimate a password's bit entropy, brute-force time and strength tier. All computation happens in your browser.
Scientific Notation Converter
Convert between standard decimal numbers and scientific notation, with significant figures and order of magnitude.
Permutations & Combinations (nPr / nCr) Calculator
Compute permutations P(n,r), combinations C(n,r) and factorial n! — useful for probability problems, lottery odds and combinatorics homework.
Standard Deviation Calculator
Paste a list of numbers to compute mean, median, sample and population variance and standard deviation — with the working shown.
Triangle Calculator (SSS / SAS / ASA)
Solve a triangle from 3 sides, 2 sides + 1 angle, or 2 angles + 1 side — area, perimeter and remaining parts via the law of sines / cosines.
Pythagorean Theorem Calculator
Given any two sides of a right triangle (two legs, or one leg plus the hypotenuse), instantly find the third side, area, perimeter and the two non-right angles.
Circle Calculator (radius / diameter / circumference / area)
Enter any one of radius, diameter, circumference or area to get the other three — useful for design, engineering and DIY.
Roman Numeral Converter
Two-way conversion between Arabic numbers (1–3999) and Roman numerals (I, V, X, L, C, D, M) — handy for typesetting, chapter titles and homework.
Slope & Line Equation Calculator (y = mx + b from Two Points)
Enter two points (x₁, y₁) and (x₂, y₂) to instantly get the slope, y-intercept, line equation y = mx + b, distance, and midpoint — a classroom staple for algebra and coordinate geometry.
Birthday Paradox Calculator
Enter group size n to see the probability that at least two people share a birthday — the classic birthday problem.
Logarithm Calculator (log / ln / log₂ / any base)
Compute logₐ(x) for any base — natural log (ln), common log (log₁₀), binary log (log₂) and a custom base, with the change-of-base steps shown.
Z-Score (Standard Score) Calculator
Enter a value, the mean and the standard deviation to compute the z-score and the corresponding normal-distribution percentile and probabilities.
Screen Pixel Density (PPI) Calculator
Enter the screen resolution and diagonal size to get pixel density (PPI), real width/height, dot pitch and total pixel count.
Hong Kong Mark Six Odds Calculator
Enter the number of tickets / selections and see the actual probability of hitting first, second … prizes in a Mark Six (6-of-49) draw.
Decimal to Fraction Converter
Convert any decimal (including repeating decimals) to a simplified fraction and a mixed number.
Sphere Volume & Surface Area Calculator
Give a sphere any one of radius, diameter, surface area or volume and instantly get the other three — plus the great-circle circumference and area.
Cylinder Volume & Surface Area Calculator
Enter the radius and height of a cylinder to get volume (π r²h), lateral surface, base area and total surface area.
Permutations (nPr) Calculator
Compute nPr — the number of ordered arrangements of r items chosen from n — alongside n!, r! and the related combination nCr.
Prime Factorization Calculator
Factor any integer from 2 up to 10¹² into primes, see the canonical exponent form, count and list all divisors.
Geometric Mean Calculator
Compute the n-th root of the product of n positive numbers — the right average for growth rates, returns and ratios — alongside the arithmetic mean for comparison.
Fibonacci Sequence Calculator
Enter any integer n from 0 to 1500 to instantly compute F(n) and F(n−1) with BigInt precision, the consecutive-term ratio (converging to the golden ratio φ) and the first 30 terms of the sequence.
Dice Roll Probability Calculator
Pick the number of dice, sides (d4 / d6 / d8 / d10 / d12 / d20) and a target sum to compute the probability of rolling exactly that total, at least, or at most.
Arithmetic Series Calculator
Enter first term a, common difference d and number of terms n to compute the nth term aₙ and the partial sum Sₙ = n/2·(2a + (n − 1)d).
Survey Sample Size Calculator
Enter confidence level, margin of error, expected proportion (and optional population size) to compute the survey sample size you need.
Geometric Series Sum Calculator
Enter the first term a, common ratio r and number of terms n to find the sum of the first n terms of a geometric series — plus the infinite-series sum when |r| < 1.
Cone Volume & Surface Area Calculator
Enter base radius and height to get the cone volume, slant height, lateral, base and total surface area.
Music Note Frequency Calculator
Pick a note (C, C♯, D, …), octave and tuning reference A4 (440 Hz by default) and the tool returns the frequency in Hz, the wavelength in air and the MIDI note number via f = A4 × 2^((n − 69)/12).
Linear Interpolation Calculator (Lerp)
Enter two known points (x₁, y₁) and (x₂, y₂) and a target x to instantly read off y via y = y₁ + (x − x₁)(y₂ − y₁)/(x₂ − x₁) — the tool flags whether your x sits inside the two points (interpolation) or outside (extrapolation).
Trapezoid Area Calculator
Enter the two parallel sides and height of a trapezoid to get its area, midsegment length and perimeter when the legs are known.
Binomial Probability Calculator
Enter the number of trials n, the per-trial success probability p and a target number of successes k to get P(X = k), P(X ≤ k), P(X ≥ k) along with the distribution mean and standard deviation.
Pearson Correlation Coefficient Calculator
Paste two parallel data series (X and Y) and get the Pearson correlation coefficient r, r², the best-fit line slope and intercept, and the sample means and standard deviations.
Confidence Interval for the Mean Calculator
Enter the sample mean, sample standard deviation, sample size and confidence level to compute a confidence interval for the population mean using the t (or z) distribution, with margin of error and standard error.
Cohen's d Effect Size Calculator
Enter the means, standard deviations and sample sizes of two groups to compute Cohen's d and Hedges' g effect sizes, classified per Cohen 1988 as trivial / small / medium / large.
Modulo (Remainder) Calculator
Enter dividend a and divisor n to compute the quotient and remainder a mod n. The truncated (C / JavaScript %), floored (Python / mathematical) and Euclidean conventions are shown side by side so the negative-input differences are obvious.
chmod Permission Converter (Octal ↔ rwx)
Toggle read/write/execute for user, group and other to instantly get both octal (e.g. 755) and symbolic (e.g. rwxr-xr-x) notations.
Vector Magnitude & Direction Calculator (2D / 3D)
Enter 2D or 3D vector components (x, y, z) to compute the magnitude, unit vector and direction angles.
Percent Error Calculator (Percent Error & Percent Difference)
Enter experimental and theoretical (accepted) values to get absolute percent error, signed relative error, and absolute error. Switch to percent-difference mode to compare two measurements where neither is the accepted value.
Poisson Distribution Probability Calculator
Enter the mean event rate λ and an event count k to get P(X = k), P(X ≤ k), P(X ≥ k), the mean, variance and standard deviation — useful for queueing, call-centre staffing and rare-event modelling.
Bayes’ Theorem Probability Calculator
Enter the prior P(A), the sensitivity P(B|A) and the false-positive rate P(B|¬A); the tool applies Bayes’ theorem to give the posterior P(A|B) — handy for medical tests, spam filters and any classification decision.
Arc Length & Sector Area Calculator
Enter a circle’s radius and central angle (degrees or radians) to compute the arc length s = r·θ, sector area A = ½·r²·θ and chord length — useful for geometry, machining and architectural layout.
Matrix Determinant Calculator (2×2 and 3×3)
Enter the entries of a 2×2 or 3×3 matrix and instantly get the determinant det(A) via ad − bc or cofactor expansion along the first row, with an invertibility check and the step-by-step 2×2 minors shown for linear-algebra study.
Vector Dot Product Calculator (2D / 3D)
Enter two 2D or 3D vectors and instantly compute the dot product, included angle, scalar projection and vector projection — with hints for orthogonal, parallel and anti-parallel cases.
Percent Difference Calculator (Symmetric)
Enter two values and compute the symmetric percent difference |a − b| / ((|a| + |b|) / 2) alongside the directional percent change (b − a)/a — a common source of confusion in lab reports and news headlines.
Vector Cross Product Calculator (3D)
Enter two 3D vectors a and b, compute the cross product a × b together with its magnitude (the area of the parallelogram they span) and sin θ — the workhorse of physics torque, computational geometry and 3D graphics.
Distance Between Two Points Calculator (2D / 3D)
Enter two points in the plane or in 3D space and the tool returns the straight-line Euclidean distance √Σ(Δᵢ)², each axis delta and the midpoint — handy for geometry homework, CAD measurements and planar GIS work.
Coefficient of Variation Calculator (CV)
Enter a dataset and the tool returns the coefficient of variation CV = σ / μ × 100% (standard deviation divided by mean) — the standard yardstick for comparing dispersion across datasets with different units or magnitudes (lab repeatability, portfolio risk).
Median, Quartiles & IQR Calculator
Enter a dataset and the tool sorts it and returns the median, first and third quartiles, the inter-quartile range (IQR) and Tukey 1.5×IQR outlier fences — the five-number summary behind every box plot.
Harmonic Mean Calculator
Enter a set of positive numbers and compute the harmonic mean HM = n / Σ(1/xᵢ) alongside the arithmetic and geometric means — the right average when the data behaves like rates or denominators (speeds, P/E ratios, flow rates).
Regular Polygon Calculator (Area, Angles, Radii)
Enter the side count n and side length s of a regular polygon and the tool returns the interior and exterior angles, the apothem and circumradius, the area and the perimeter in one shot — works for triangles, squares, pentagons, hexagons and beyond.