Catalan Number Calculator
Calculate the nth Catalan number or generate a sequence of Catalan numbers. Get exact integer results and learn the mathematical formulas behind the sequence.
Calculate Catalan Numbers
Select a calculation mode, enter your value, and click the calculate button. The result will appear below the form.
What Is a Catalan Number?
Catalan numbers are a sequence of integers that occur in combinatorics, the branch of mathematics concerned with counting arrangements and structures. The sequence begins:
The first value is C0 = 1. The next is C1 = 1, followed by C2 = 2 and C3 = 5. Catalan numbers are used to count balanced parentheses, binary trees, polygon triangulations, and many other structures.
Catalan Number Formula
The closed-form formula for the nth Catalan number is:
Equivalently, using a binomial coefficient:
Here, n is a non-negative integer and the exclamation mark denotes a factorial. For example, 5! = 5 × 4 × 3 × 2 × 1 = 120.
Catalan Number Recurrence Relation
Catalan numbers can be calculated one at a time without directly evaluating large factorials. The recurrence relation is:
Cn = Cn−1 × 2(2n − 1) / (n + 1)
For every integer n greater than or equal to 1, this recurrence produces the next Catalan number from the previous one. The division is exact. This calculator uses this relation together with decimal-string arithmetic to avoid ordinary PHP integer overflow.
Example Calculation: C5
Starting with C0 = 1:
C2 = 1 × 2 × 3 / 3 = 2
C3 = 2 × 2 × 5 / 4 = 5
C4 = 5 × 2 × 7 / 5 = 14
C5 = 14 × 2 × 9 / 6 = 42
Therefore, the fifth Catalan number is C5 = 42.
First 11 Catalan Numbers
| n | Cn |
|---|---|
| 0 | 1 |
| 1 | 1 |
| 2 | 2 |
| 3 | 5 |
| 4 | 14 |
| 5 | 42 |
| 6 | 132 |
| 7 | 429 |
| 8 | 1430 |
| 9 | 4862 |
| 10 | 16796 |
Applications of Catalan Numbers
- Balanced parentheses: count valid arrangements of n pairs of parentheses.
- Binary trees: count structurally distinct full binary trees with n internal nodes.
- Polygon triangulation: count triangulations of a convex polygon with n + 2 vertices.
- Lattice paths: count paths that remain on one side of a diagonal.
- Expression grouping: count ways to fully parenthesize an ordered sequence of factors.
Frequently Asked Questions
What is C0?
C0 equals 1. It is the starting value of the Catalan sequence.
Can I calculate a large Catalan number?
Yes. Single-number mode accepts indices from 0 through 500. The calculator uses string arithmetic to preserve the exact decimal result.
Can I generate multiple Catalan numbers?
Yes. Select the sequence option and enter the number of terms you need. The calculator generates the sequence beginning with C0.
Does this calculator need a PHP extension?
No. It uses standard PHP functionality and does not require BCMath, GMP, a database, or a third-party library.