Catalan Numbers

Catalan number computation via closed-form formula and DP recurrence.

[Combinatorics]|

Jul 9, 2026

|explanatory_notes.md|

#catalan#combinatorics#counting

$cat source_code/

cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll MOD = 1e9 + 7;

ll power(ll base, ll exp, ll mod) {
    ll res = 1; base %= mod;
    while (exp > 0) {
        if (exp & 1) res = res * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return res;
}

ll modInv(ll x) { return power(x, MOD - 2, MOD); }

ll catalan(ll n) {
    ll res = 1;
    for (ll i = 0; i < n; i++)
        res = res % MOD * ((2 * n - i) % MOD) % MOD * modInv(i + 1) % MOD;
    return res % MOD * modInv(n + 1) % MOD;
}

const int MAXCAT = 5005;
ll cat_dp[MAXCAT];

void initCatalanDp(int n) {
    cat_dp[0] = cat_dp[1] = 1;
    for (int i = 2; i <= n; i++)
        for (int j = 0; j < i; j++)
            cat_dp[i] = (cat_dp[i] + cat_dp[j] * cat_dp[i - j - 1]) % MOD;
}

34 linesutf-8

$cat explanation_notes.md

notes_viewer --renderedmarkdown (math enabled)

Catalan Numbers

Sequence: $1, 1, 2, 5, 14, 42, 132, 429, 1430, \ldots$

Formulas

Closed form:

C_n = \frac{1}{n+1} \binom{2n}{n}

Recurrence:

C_{n+1} = \sum_{i=0}^{n} C_i \cdot C_{n-i}

Classic Applications

Balanced bracket sequences with

n

pairs

Distinct binary tree shapes with

n

nodes

Triangulations of an

(n+2)

-gon

Dyck paths (lattice paths staying below diagonal)

Number of full binary trees with

n+1

leaves

Two Methods

catalan(n) — direct formula,

O(n)

with precomputed factorials or

O(n \log \text{MOD})

standalone

initCatalanDp() — DP table for small

n

O(n^2)

Complexity

Formula —

O(n)

(with factorial precomp) or

O(n \log p)

standalone

DP —

O(n^2)