Catalan number

Lore & Background

The Catalan numbers are named after Eugène Catalan, though they were previously discovered in the 1730s by Minggatu. The n-th Catalan number can be expressed directly in terms of the central binomial coefficients as C_n = 1/(n+1) * binomial(2n, n) = (2n)! / ((n+1)! n!) for n ≥ 0. The first Catalan numbers for n = 0, 1, 2, 3, ... An alternative expression is C_n = binomial(2n, n) - binomial(2n, n+1), which shows that C_n is an integer. Another alternative expression is C_n = 1/(2n+1) * binomial(2n+1, n). The Catalan numbers satisfy recurrence relations: C_0 = 1 and C_n = sum_{i=1}^n C_{i-1} C_{n-i} for n > 0, as well as C_0 = 1 and C_n = (2(2n-1)/(n+1)) C_{n-1} for n > 0.

Reader's Guide

The Catalan numbers are significant as a fundamental sequence in combinatorics, appearing in many counting problems involving recursively defined objects. Their asymptotic growth is C_n ~ 4^n / (n^(3/2) sqrt(pi)), which can be proved using Stirling's approximation or generating functions. The only Catalan numbers that are odd are those for which n = 2^k - 1; all others are even. The only prime Catalan numbers are C_2 = 2 and C_3 = 5. The multiplicity with which a prime p divides C_n can be determined by expressing n+1 in base p, with specific rules for counting digits depending on p. The Catalan numbers also have integral representations, such as C_n = 1/(2π) ∫_0^4 x^n sqrt((4-x)/x) dx.

Did You Know?

• The Catalan numbers were discovered in the 1730s by Minggatu before being named after Eugène Catalan.
• The only prime Catalan numbers are C_2 = 2 and C_3 = 5.
• The only Catalan numbers that are odd are those for which n = 2^k - 1.
• The Catalan numbers satisfy the recurrence C_n = (2(2n-1)/(n+1)) C_{n-1} for n > 0.

Origins and the Question of Credit

The Catalan numbers carry a name that obscures their true age. The sequence is universally credited to Eugène Catalan, yet the facts show that the numbers were first identified in the 1730s by Minggatu, placing the initial discovery well before Catalan's era. This gap between first identification and lasting attribution is a small but instructive reminder of how mathematical credit often trails actual discovery. The sequence itself is a family of natural numbers that surfaces across a broad range of counting problems, especially those built around recursively defined objects. Rather than living in a single corner of mathematics, the Catalan numbers act as a connective thread, appearing wherever combinatorial enumeration meets self-similar construction. Their listing under sequence A000108 in the OEIS has cemented their status as a standard reference point for anyone exploring recursive combinatorics, and the dual naming history adds a layer of historical texture to what is otherwise a purely structural object.

Closed Forms and the Integer Question

The most celebrated closed-form expression for the n-th Catalan number divides the central binomial coefficient (2n choose n) by n + 1, giving C_n = (2n)! / ((n+1)! n!) for every n ≥ 0. At a glance this fraction could plausibly yield a non-integer, yet every term in the sequence is a whole number. The resolution arrives through an alternative formulation: C_n equals (2n choose n) minus (2n choose n+1). This difference-of-binomials identity is algebraically equivalent to the original because (2n choose n+1) can be rewritten as (n/(n+1)) times (2n choose n). Subtracting that scaled copy from the full binomial coefficient naturally produces an integer, and this equivalence forms the backbone of the standard correctness proof. A third equivalent form, C_n = (1/(2n+1)) × (2n+1 choose n), ties the sequence directly to the cycle lemma, offering yet another lens on why these numbers behave so cleanly.

Two Recurrences, Two Perspectives

What gives the Catalan numbers a sense of internal life is their recursive architecture. Beginning with C_0 = 1, every later term can be assembled by summing products of earlier terms: C_n equals the sum, over i from 1 to n, of C_{i−1} times C_{n−i}. This convolution-style recurrence mirrors the way many recursively defined combinatorial objects are built, where a larger structure splits into a left component and a right component, each independently drawn from smaller instances. A second, more compact recurrence links each term directly to its immediate predecessor: C_n = [2(2n−1)/(n+1)] × C_{n−1}. This ratio form is computationally economical, needing only a single multiplication and division to step forward. Together the two recurrences capture both the structural decomposition and the smooth numerical growth of the sequence, and they underpin much of the theoretical work connecting Catalan numbers to broader combinatorial identities.

Growth, Values, and Combinatorial Reach

The opening stretch of the sequence — 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786 — accelerates at a pace that is neither purely exponential nor polynomial. Asymptotically, the n-th Catalan number behaves like 4^n divided by n to the three-halves power times the square root of pi. In precise terms, the ratio of C_n to that expression approaches 1 as n grows without bound, a result that follows from the asymptotic behavior of the underlying binomial coefficients. This growth rate sits between the raw exponential 4^n and the slower polynomial damping, giving the sequence a distinctive combinatorial fingerprint. Because the Catalan numbers arise in so many different counting problems involving recursively defined objects, they function as a kind of universal yardstick in enumerative combinatorics, and their asymptotic profile helps calibrate expected structure sizes across a wide variety of discrete models.

Gallery