Catalan Number Calculator

Find the nth Catalan number.

Index (n)

Results update as you type.

nth Catalan number

—

How it works

Catalan numbers are one of the most important sequences in combinatorics, appearing in a surprising range of counting problems, and this calculator computes any term. You enter the index n, and it returns the nth Catalan number. The sequence begins 1, 1, 2, 5, 14, 42, 132, 429, and grows rapidly. Each term equals the binomial coefficient 2n choose n divided by n plus one, and the calculator uses a numerically stable product form to compute it accurately without overflowing on factorials. What makes Catalan numbers remarkable is how many different structures they count. The nth Catalan number is the number of valid ways to arrange n pairs of parentheses, the number of distinct binary trees with n nodes, the number of ways to triangulate a polygon with n plus 2 sides, the number of paths that stay above the diagonal on a grid (monotonic lattice paths that do not cross), and the number of ways a convex polygon can be cut into triangles, among many others. This deep unity across seemingly unrelated problems is why Catalan numbers are famous in mathematics and computer science, where they appear in analyzing recursive algorithms and data structures. This calculator is useful for students of combinatorics, programmers reasoning about tree structures, and anyone exploring these counting problems. Enter an index to compute its Catalan number.

Formula

C(n) = (2n)! / ((n + 1)! × n!) = C(2n, n) / (n + 1)

The nth Catalan number equals the binomial coefficient 2n choose n divided by n plus one. The calculator computes it with a stable product to avoid factorial overflow. The sequence is 1, 1, 2, 5, 14, 42, 132, and so on.

Source:Combinatorics

We review all our tools from time to time to ensure accuracy.

Worked example

Index (n):5

C(5) = C(10,5) / 6 = 252 / 6 = 42.

How to use this calculator

1
Enter your values
Enter index (n).
2
Adjust the options
Fine-tune any options to match your situation.
3
Read your result
nth Catalan number updates instantly as you type — no button to press.

Frequently asked questions

What are Catalan numbers?

Catalan numbers are a sequence in combinatorics: 1, 1, 2, 5, 14, 42, 132, and so on. The nth term equals the binomial coefficient 2n choose n divided by n plus one. They count an astonishing variety of recursive structures, which makes them one of the most important and frequently occurring sequences in mathematics.

What do Catalan numbers count?

The nth Catalan number counts the ways to correctly match n pairs of parentheses, the number of binary trees with n nodes, the triangulations of a polygon with n plus 2 sides, certain lattice paths that stay above a diagonal, and many other structures. This wide applicability across unrelated-seeming problems is a hallmark of Catalan numbers.

How is the nth Catalan number calculated?

Divide the binomial coefficient 2n choose n by n plus one. For n equals 5, that is 10 choose 5, which is 252, divided by 6, giving 42. The calculator uses a stable step-by-step product so it can compute Catalan numbers for larger n without the overflow that computing full factorials would cause.

Why are Catalan numbers important in computer science?

They arise in analyzing recursive data structures and algorithms, most notably in counting the number of distinct binary trees or binary search trees with a given number of nodes, and in problems involving balanced parentheses or expression parsing. Understanding Catalan numbers helps in complexity analysis and combinatorial reasoning about such structures.

How fast do Catalan numbers grow?

Catalan numbers grow rapidly, roughly like 4 to the n divided by n to the power of 1.5 times a constant, so they increase almost as fast as an exponential. This quick growth reflects the combinatorial explosion in the number of recursive structures as size increases, which is why they appear in complexity analysis of recursive problems.