Catalan Numbers Calculator

Compute Catalan numbers C_n = (2n)!/((n+1)! n!), Segner recurrence, asymptotic formula 4^n/(sqrt(pi) n^1.5) and over 200 combinatorial interpretations.

Calculation parameters
Scegli il tipo di calcolo.
Indice del numero di Catalan. 0 e' il primo, C_0 = 1. Max 25 per calcolo esatto (C_25 supera 2^63).
Numero di termini C_0 ... C_N da mostrare. Max 30.
Was this calculator useful?

The Catalan numbers

The Catalan numbers, denoted C_n (n = 0, 1, 2, ...), are one of the most important sequences in enumerative combinatorics. Defined by:

C_n = (1/(n+1)) · (2n)!/(n! n!) = (1/(n+1)) · (2n choose n)

First terms: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, ... The name honours Eugene Charles Catalan (1838), but they were studied earlier by Euler (1751) and Segner (1758). In China, Minggatu studied them around 1730.

The four modes

  1. Single C_n: compute one Catalan number via closed form and show equivalent formulas.
  2. Table: list the first N+1 terms with the ratio C_(n+1)/C_n tending to 4.
  3. Segner recurrence check: C_(n+1) = sum_(i=0..n) C_i · C_(n-i) vs the closed form.
  4. Combinatorial interpretations: lists meanings of C_n — balanced parens, binary trees, Dyck paths, triangulations, etc.

Euler's formula and Segner's recurrence

Euler (1751) noticed that the number of ways to triangulate a convex polygon with n+2 sides satisfies a simple recurrence. Segner (1758) formalised it:

C_(n+1) = C_0 · C_n + C_1 · C_(n-1) + ... + C_n · C_0

with C_0 = 1. This discrete convolution generalises via the generating function c(x) = sum C_n x^n satisfying c(x) = 1 + x · c(x)^2. Solving the quadratic: c(x) = (1 - sqrt(1 - 4x))/(2x). Taylor expansion gives all C_n and an elegant proof of the closed form.

Closed form and asymptotics

Closed form: C_n = (1/(n+1)) (2n choose n). Equivalent: C_n = (2n choose n) − (2n choose n+1) by the reflection principle. For large n, applying Stirling:

C_n ~ 4^n / (sqrt(pi) · n^(3/2))

Ratio C_(n+1)/C_n = (4n+2)/(n+2) → 4. Exponential growth with fractional power factor — typical of many combinatorial sequences arising in random walks, discrete Brownian motion, polymer models.

Over 200 combinatorial interpretations

Richard Stanley in Enumerative Combinatorics (vol. 2, 1999) catalogues over 200 combinatorial interpretations:

  • Balanced parentheses: number of well-formed n-pair sequences. For n = 3: ((())), (()()), (())(), ()(()), ()()() = 5 = C_3.
  • Binary trees: binary trees with n internal nodes (n+1 leaves).
  • Dyck paths: monotonic lattice paths from (0,0) to (2n,0) with +1/-1 steps never going below x-axis.
  • Polygon triangulations: ways to triangulate a convex (n+2)-gon with non-crossing diagonals.
  • Parenthesisations: ways to parenthesise n+1 factors x_0 · x_1 · ... · x_n.
  • Stack-sortable permutations: permutations of {1,...,n} avoiding pattern 231.
  • Non-crossing chords: ways to draw n chords between 2n points on a circle with no crossings.
  • Standard Young tableaux of shape 2 × n.
  • Non-crossing partitions: pairings of 2n points on a line without crossings.
  • Mountain profiles: n ups and n downs of unit length staying above start level.

Each interpretation yields a combinatorial bijection connecting apparently different discrete structures.

Modern applications

  • Theoretical CS: data structures, parsers, balanced context-free languages.
  • Molecular biology: non-crossing RNA secondary structures are C_n / n for n base pairs.
  • Financial maths: American option pricing with binomial trees.
  • Representation theory: irrep dimensions of the symmetric group, Young tableaux.
  • Random walks: first returns to origin in 1D symmetric random walks.
  • Graph theory: triangulations, planar Tutte structures.

Quadratic ratio recurrence

A recurrence useful for numerical computation:

C_(n+1) = ((4n+2)/(n+2)) · C_n

Avoids explicit factorials. Starting from C_0 = 1: C_1 = 2/2 = 1, C_2 = 6/3 · 1 = 2, C_3 = 10/4 · 2 = 5, ... Efficient and numerically stable up to n ~ 30.

Updated July 2026

Frequently Asked Questions

What are Catalan numbers?

They are a sequence of integers C_n = 1, 1, 2, 5, 14, 42, 132, ... fundamental in enumerative combinatorics. The closed form is C_n = (1/(n+1)) (2n choose n) = (2n)!/((n+1)! n!). They are named after Eugene Charles Catalan (1838), but were already known to Minggatu, Euler and Segner in the 18th century.

What modes does the calculator offer?

Four: the single C_n with closed form and asymptotic ratio, the table of the first N+1 terms, the verification of Segner's recurrence by convolution, and the combinatorial interpretations of the number. It also gives equivalent formulas and the error relative to the asymptotic approximation.

How is a Catalan number computed?

With the closed form C_n = (2n choose n)/(n+1), or with the quotient recurrence C_(n+1) = (2(2n+1)/(n+2)) C_n that avoids factorials. A third method is Segner's recurrence C_(n+1) = sum of C_i times C_(n-i), which reflects the recursive structure of the counted objects.

What do Catalan numbers count?

An enormous variety of structures: the sequences of n well-formed pairs of parentheses, binary trees with n internal nodes, Dyck paths, triangulations of a polygon with n+2 sides, ways to parenthesize a product of n+1 factors, and non-crossing chords between 2n points. Richard Stanley catalogued over 200 of them.

Why does the ratio C_(n+1)/C_n tend to 4?

Because the generating function C(x) = (1 - sqrt(1-4x))/(2x) has a singularity at x = 1/4. In generating-function theory the singularity nearest the origin determines the growth of the coefficients, hence the factor 4^n. Consequently the ratio between consecutive terms progressively approaches 4.

What is the asymptotic formula?

It is the approximation C_n about 4^n / (sqrt(pi) n^(3/2)), obtained by applying Stirling's formula to the closed form. It describes the exponential growth rate tempered by the polynomial factor n^(3/2). Even for moderate values of n it gives an estimate with small relative error, which the calculator shows.

Who discovered the Catalan numbers?

They were found independently in different places: by the Mongolian mathematician Minggatu around 1730 in China, by Euler around 1751 studying polygon triangulations, and formalized with the recurrence by Segner in 1758. The name comes from Eugene Charles Catalan, who studied them in 1838.

Where are Catalan numbers used?

In theoretical computer science for parsers and expressions, in tree data structures, in molecular biology for RNA secondary structures, in financial mathematics for American option pricing, in representation theory with Young tableaux, and in the study of random walks.

Comments (0)

No comments yet. Be the first!