Some numbers keep showing up in unrelated places: the same sequence counts the ways to put brackets round a product, to cut a polygon into triangles and to draw a path that never crosses the diagonal. These are the Catalan numbers. This calculator gives the Catalan number for a chosen n, the structures it counts, the central binomial coefficient it comes from and a simple approximation with its error.
How the calculation works
- Catalan number C(n) = (2n)! ÷ ((n + 1)! × n!) = C(2n, n) ÷ (n + 1)
- Triangulations of a convex polygon with n + 2 sides = C(n)
- Parenthesizations of a product of n + 1 factors = C(n)
- Approximation C(n) ≈ 4ⁿ ÷ (n^1.5 × √π)
- Growth ratio C(n) ÷ C(n − 1) tends to 4
Example
For n = 10, the Catalan number is 16,796. It counts the ways to triangulate a 12-sided polygon, the ways to put brackets round a product of 11 factors, and the valid sequences of 10 pairs of brackets. The central binomial coefficient C(20, 10) is 184,756, and the approximation gives about 18,708, which is 11.4 % too high. The ratio C(10) ÷ C(9) is 3.455, already close to 4.
Why it matters
Catalan numbers are the answer to a surprising number of counting problems, from the structure of expressions in a compiler to the shapes of binary search trees. Knowing the growth rate warns you that brute-force listing quickly becomes impossible: C(20) is already 6.5 billion. The approximation gives a feel for the size without computing factorials.
Good to know
The calculator is exact up to n = 17, where the number fits comfortably in the precision of the calculation. The approximation improves slowly, with an error of about 1/(8n). Different counting problems give the same numbers only when they are set up with the right constraint, such as a path that stays on one side of the diagonal. This tool is for education.
In practice
To check a counting problem, work out the first four values by hand and compare with 1, 2, 5, 14: if they match, a Catalan number is likely. For the number of different ways to evaluate an expression with n operations, use C(n).
Related tools
The permutations calculator, the Fibonacci calculator and the arithmetic and geometric series calculator cover other classic counting sequences.