Skip to content
Omnikalc

Catalan number calculator: C(n) and what it counts

Enter n to get the Catalan number, the number of polygon triangulations and bracketings it counts, the central binomial coefficient and an approximation.

Updated on
Your inputs

Value out of range

Results

Catalan number C(n)

16,796

Ways to triangulate a convex polygon with n + 2 sides
16,796
Ways to parenthesize a product of n + 1 factors
16,796
Central binomial coefficient C(2n, n)
184,756
Approximation 4ⁿ ÷ (n^1.5 × √π)
18,708
Error of the approximation
11.4%
Ratio C(n) ÷ C(n − 1) (tends to 4)
3.455

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).

The permutations calculator, the Fibonacci calculator and the arithmetic and geometric series calculator cover other classic counting sequences.

Frequently asked questions

What are the Catalan numbers?

They are the sequence 1, 1, 2, 5, 14, 42, 132, 429, … that counts many structures: ways to parenthesize a product, binary trees with n nodes, triangulations of a polygon, paths on a grid that stay below the diagonal, and valid sequences of n pairs of brackets.

How is a Catalan number calculated?

C(n) = (2n)! ÷ ((n + 1)! × n!), which equals C(2n, n) ÷ (n + 1). The first values are 1, 1, 2, 5, 14, 42, 132, 429, 1430 and 4862, and C(10) is 16,796.

How many triangulations does a polygon have?

A convex polygon with n + 2 sides can be split into triangles in C(n) ways. A hexagon (n = 4) has 14 triangulations and an octagon (n = 6) has 132.

How fast do they grow?

Each term is about 4 times the previous one, because C(n) is close to 4ⁿ ÷ (n^1.5 × √π). The ratio between neighbouring terms tends to 4, which is why they overtake most other counting sequences very quickly.

Was this calculator helpful?

Thanks for your feedback!

Results are estimates provided for information purposes. They do not replace professional advice.