Symbolic Method — Analytic Combinatorics Basics

January 2026 · 28 min read

What Is the Symbolic Method?

The symbolic method, developed by Philippe Flajolet and Robert Sedgewick in their landmark Analytic Combinatorics (2009), provides a systematic pipeline for counting combinatorial objects:

1. Specify the combinatorial class using a formal grammar of constructions.
2. Translate each construction into an equation on generating functions — mechanically, with no guesswork.
3. Analyse the generating function (GF) to extract exact counts or asymptotics.

The beauty of the approach is that step 2 is entirely automatic. Once you describe what objects look like (step 1), a dictionary of translation rules produces the GF equation. You never need an ad-hoc bijection or a flash of insight — the dictionary does the work.

For competitive programming, this means: if you can decompose a structure into smaller pieces using unions, products, sequences, etc., the GF pops out for free. From there you can read off coefficients (exact counts), derive recurrences, or apply singularity analysis for asymptotics.

Why should CP contestants care?

Many DP-based counting problems are secretly asking you to count objects in a combinatorial class. Recognising the underlying construction can:

• Immediately give you a closed-form GF, bypassing DP derivation entirely.
• Reveal that two seemingly different problems share the same GF (e.g., Catalan structures).
• Suggest an O(n log n) NTT-based solution when the GF factors as a convolution.
• Provide asymptotic bounds useful for estimating answer sizes or proving feasibility.

Admissible Constructions

An admissible construction is one that preserves the size of objects in a predictable way, so the translation to GFs is well-defined. Flajolet and Sedgewick identified the following core constructions. Each has a direct translation for both ordinary generating functions (OGF, unlabelled) and exponential generating functions (EGF, labelled).

The Translation Dictionary (Unlabelled / OGF)

The Translation Dictionary (Labelled / EGF)

Composability

These constructions can be nested. For example, a set of cycles is Perm = Set(Cyc(𝒵)). The EGF translation gives:

&Pcirc;(z) = exp(log(1/(1−z))) = 1/(1−z) = Σ_n≥0 n! · zⁿ/n!

which confirms the well-known fact that there are n! permutations of size n. This kind of one-line derivation is the power of the symbolic method.

Unlabelled vs Labelled

The choice between OGF and EGF depends on whether the atoms in your objects are distinguishable.

Example: Binary Strings (OGF)

A binary string is a sequence of bits, where each bit is either 0 or 1. The atom class is ℬ = {0, 1}, so B(z) = 2z (two atoms of size 1). A binary string is Seq(ℬ):

S(z) = 1/(1 − 2z) = Σ_n≥0 2ⁿ zⁿ

confirming that there are 2ⁿ binary strings of length n. No labels involved — pure OGF.

Example: Permutations (EGF)

A permutation of [n] is a sequence of distinct labelled atoms. The atom class is 𝒵 with EGF z. A permutation is Seq(𝒵):

&Pcirc;(z) = 1/(1 − z) = Σ_n≥0 zⁿ

Reading off the coefficients: a_n/n! = 1, so a_n = n!. Exactly right.

Worked Examples

(a) Binary Trees & Catalan Numbers

A (full) binary tree is either a single leaf or an internal node with a left subtree and a right subtree. Letting 𝒯 denote the class, with the size being the number of internal nodes:

𝒯 = ℰ + 𝒵 × 𝒯 × 𝒯

Translating via the OGF dictionary:

T(z) = 1 + z · T(z)²

This is a quadratic in T(z). Solving:

T(z) = (1 − √(1 − 4z)) / (2z)

(We pick the − root because T(0) must be finite.) Expanding via the generalised binomial theorem gives:

[zⁿ] T(z) = C_n = C(2n, n) / (n+1)

— the Catalan numbers: 1, 1, 2, 5, 14, 42, 132, …

(b) Set Partitions & Bell Numbers

A set partition of [n] is a collection of non-empty, disjoint subsets (blocks) whose union is [n]. In the symbolic framework (labelled):

Partition = Set(Block),   Block = Set_≥1(𝒵)

The EGF of a non-empty set of atoms is e^z − 1 (subtract the empty set). A set partition is a set of blocks:

&Pcirc;(z) = exp(e^z − 1)

The coefficient [zⁿ/n!] gives the Bell number B_n. The first few values: 1, 1, 2, 5, 15, 52, 203, 877, …

This single line — exp(e^z − 1) — replaces the entire Bell triangle recurrence and immediately shows the structure.

(c) Permutations by Cycles

Every permutation decomposes uniquely into a set of disjoint cycles. In the symbolic method:

Perm = Set(Cyc(𝒵))

The EGF of a cycle of labelled atoms is Cyc(𝒵) → log(1/(1−z)). Then:

&Pcirc;(z) = exp(log(1/(1−z))) = 1/(1−z)

As expected. But the decomposition is far more powerful than just counting permutations — it lets us count permutations by number of cycles. If we mark each cycle with a variable u:

&Pcirc;(z, u) = exp(u · log(1/(1−z))) = (1/(1−z))^u

The coefficient [zⁿ/n!] u^k is the (unsigned) Stirling number of the first kind [ⁿ/_k], counting permutations of n elements with exactly k cycles.

(d) Integer Compositions

A composition of n is an ordered tuple of positive integers summing to n. Symbolically:

Comp = Seq(Seq_≥1(𝒵))

Seq_≥1(𝒵) has OGF z/(1−z). Then:

C(z) = 1/(1 − z/(1−z)) = (1−z)/(1−2z)

So [zⁿ] C(z) = 2ⁿ⁻¹ for n ≥ 1, which matches the well-known result that there are 2ⁿ⁻¹ compositions of n.

Singularity Analysis

Once we have a generating function, we often want asymptotics — how fast does a_n grow? The key tool from analytic combinatorics is singularity analysis: the growth rate of [zⁿ] f(z) is governed by the singularity of f(z) closest to the origin.

Dominant Singularity Principle

If f(z) is analytic in a disc of radius R, then [zⁿ] f(z) grows roughly as R⁻ⁿ. The singularity at |z| = R — the dominant singularity — controls the exponential growth rate.

Example: Catalan Number Asymptotics

The GF T(z) = (1 − √(1−4z)) / (2z) has a dominant singularity at z = 1/4 (branch point of the square root). Near z = 1/4:

T(z) ~ 1/(2z) · (1 − (1−4z)^1/2)

The singular part behaves like (1 − 4z)^1/2 with α = 1/2. Applying the transfer theorem with ρ = 1/4:

C_n ~ 4ⁿ / (n√(πn))

This asymptotic is remarkably accurate even for moderate n. For n = 10, the true value is 16796 and the estimate gives ≈ 16724.

Exponential Growth Table

Some common GFs and their growth rates derived by singularity analysis:

Multiple Singularities

When there are several singularities on the circle of convergence, their contributions add. For example, the GF 1/(1−z²) = 1/((1−z)(1+z)) has singularities at z = 1 and z = −1. The coefficient [zⁿ] equals (1 + (−1)ⁿ)/2, which is 1 for even n and 0 for odd n — the contributions from both singularities combine to produce the oscillation.

C++ for GF Manipulation

In competitive programming, we rarely manipulate GFs symbolically at runtime. Instead, we compute the first N coefficients of a GF using polynomial arithmetic. The key operations are polynomial multiplication (via NTT), inversion, and exponentiation.

Generating Catalan Numbers via the Recurrence

From T(z) = 1 + z · T(z)², we derive the recurrence C₀ = 1, C_n = Σ_k=0ⁿ⁻¹ C_k · C_n−1−k. This is O(n²) but simple:

// O(n^2) Catalan numbers from the symbolic equation T = 1 + z*T^2
#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

vector<long long> catalan(int n) {
    vector<long long> C(n + 1);
    C[0] = 1;
    for (int i = 1; i <= n; i++) {
        C[i] = 0;
        for (int k = 0; k < i; k++) {
            C[i] = (C[i] + C[k] % MOD * C[i - 1 - k]) % MOD;
        }
    }
    return C;
}

int main() {
    int n;
    cin >> n;
    auto C = catalan(n);
    for (int i = 0; i <= n; i++)
        cout << "C[" << i << "] = " << C[i] << "\n";
}

NTT-Based Polynomial Multiplication

When we need to multiply two polynomials (= convolve two coefficient sequences) modulo a prime, NTT gives O(n log n). This is the workhorse behind fast GF manipulation.

// NTT-based polynomial multiplication mod 998244353
#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353, g = 3;

long long power(long long a, long long b, long long mod) {
    long long res = 1; a %= mod;
    for (; b > 0; b >>= 1) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
    }
    return res;
}

void ntt(vector<long long>& a, bool inv) {
    int n = a.size();
    for (int i = 1, j = 0; i < n; i++) {
        int bit = n >> 1;
        for (; j & bit; bit >>= 1) j ^= bit;
        j ^= bit;
        if (i < j) swap(a[i], a[j]);
    }
    for (int len = 2; len <= n; len <<= 1) {
        long long w = inv ? power(g, MOD - 1 - (MOD - 1) / len, MOD)
                         : power(g, (MOD - 1) / len, MOD);
        for (int i = 0; i < n; i += len) {
            long long wn = 1;
            for (int j = 0; j < len / 2; j++) {
                long long u = a[i + j];
                long long v = a[i + j + len / 2] * wn % MOD;
                a[i + j] = (u + v) % MOD;
                a[i + j + len / 2] = (u - v + MOD) % MOD;
                wn = wn * w % MOD;
            }
        }
    }
    if (inv) {
        long long n_inv = power(n, MOD - 2, MOD);
        for (auto& x : a) x = x * n_inv % MOD;
    }
}

vector<long long> multiply(vector<long long> a, vector<long long> b) {
    int result_size = a.size() + b.size() - 1;
    int n = 1;
    while (n < result_size) n <<= 1;
    a.resize(n); b.resize(n);
    ntt(a, false); ntt(b, false);
    for (int i = 0; i < n; i++) a[i] = a[i] * b[i] % MOD;
    ntt(a, true);
    a.resize(result_size);
    return a;
}

int main() {
    // Example: multiply (1 + 2z + 3z^2) by (4 + 5z)
    vector<long long> a = {1, 2, 3}, b = {4, 5};
    auto c = multiply(a, b);
    // c = {4, 13, 22, 15}  i.e. 4 + 13z + 22z^2 + 15z^3
    for (int i = 0; i < (int)c.size(); i++)
        cout << "z^" << i << ": " << c[i] << "\n";
}

Partition Numbers via Euler’s Product

The number of integer partitions of n has the famous OGF:

P(z) = Π_k=1^∞ 1/(1 − z^k)

This is MSet(𝒵 + 𝒵² + 𝒵³ + …) in the symbolic framework. We compute the first N+1 coefficients in O(N√N) using Euler’s pentagonal theorem, or in O(N log N) by taking the logarithm and using power series:

// Partition numbers p(0..N) in O(N * sqrt(N))
// Uses Euler's pentagonal recurrence:
// p(n) = sum_{k!=0} (-1)^{k+1} * p(n - k(3k-1)/2)
#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

vector<long long> partitions(int N) {
    vector<long long> p(N + 1, 0);
    p[0] = 1;
    for (int n = 1; n <= N; n++) {
        for (int k = 1; ; k++) {
            int g1 = k * (3 * k - 1) / 2;   // generalised pentagonal
            int g2 = k * (3 * k + 1) / 2;    // negative k term
            if (g1 > n) break;
            long long sign = (k % 2 == 1) ? 1 : MOD - 1;
            p[n] = (p[n] + sign * p[n - g1]) % MOD;
            if (g2 <= n)
                p[n] = (p[n] + sign * p[n - g2]) % MOD;
        }
    }
    return p;
}

int main() {
    int N;
    cin >> N;
    auto p = partitions(N);
    for (int i = 0; i <= min(N, 20); i++)
        cout << "p(" << i << ") = " << p[i] << "\n";
}

Computing Bell Numbers from the EGF

Since the EGF is exp(e^z − 1), we can compute Bell numbers by composing power-series operations: first compute the series for e^z − 1, then exponentiate it. In practice, the Bell triangle recurrence B_n+1 = Σ_k=0ⁿ C(n,k) B_k is simpler for competitive programming:

// Bell numbers via the Bell triangle — O(n^2)
#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

vector<long long> bell_numbers(int n) {
    // Bell triangle: row[0] = B_i, then row[j] = row[j-1] + prev_row[j-1]
    vector<long long> B(n + 1);
    vector<long long> row(n + 1);
    B[0] = 1;
    row[0] = 1;
    for (int i = 1; i <= n; i++) {
        vector<long long> nrow(n + 1);
        nrow[0] = row[i - 1];  // last element of previous row
        for (int j = 1; j <= i; j++) {
            nrow[j] = (nrow[j - 1] + row[j - 1]) % MOD;
        }
        B[i] = nrow[0];
        row = nrow;
    }
    return B;
}

int main() {
    int n;
    cin >> n;
    auto B = bell_numbers(n);
    for (int i = 0; i <= n; i++)
        cout << "B[" << i << "] = " << B[i] << "\n";
}

CP Applications

The symbolic method is not just a theoretical framework — it has direct, practical applications in competitive programming.

When to Use GFs vs DP

Recognising Symbolic Constructions in Problems

Many CP problems are disguised symbolic specifications. Here are some patterns to watch for:

• “Count sequences of objects where each object comes from set S” → Seq(𝒮), GF = 1/(1 − S(z)).
• “Count unordered collections (subsets, multisets)” → Set(𝒜) for labelled, MSet(𝒜) for unlabelled.
• “Count trees with a recursive structure” → Write the recursive decomposition, translate directly. E.g., ordered trees: T = 𝒵 × Seq(T).
• “Count objects up to cyclic symmetry” → Cycle construction (or Burnside/Pólya if the symmetry group is more complex).
• “Convolve two arrays of counts” → This is literally the product of two GFs. Use NTT.

Fast Convolution for Combining Sequences

A very common CP pattern: you have two sequences (a₀, …, a_n) and (b₀, …, b_m) and need c_k = Σ_i+j=k a_i · b_j. This is exactly the product of two OGFs, computable in O((n+m) log(n+m)) via NTT.

Applications include: counting paths of length k in graphs (adjacency matrix polynomial), combining independent knapsack-like constraints, and composing transfer matrices.

Lagrange Inversion

When you have an implicit equation like T(z) = z · φ(T(z)), Lagrange inversion gives:

[zⁿ] T(z) = (1/n) [wⁿ⁻¹] φ(w)ⁿ

This is how Catalan, Motzkin, and many tree-counting formulas are derived. In contests, if you arrive at an implicit GF equation, Lagrange inversion often yields a closed-form coefficient.

Summary

The symbolic method provides a mechanical translation from combinatorial descriptions to generating functions. Here is what to remember:

1. Specify objects using atoms (𝒵), union (+), product (×), Seq, Set, Cyc.
2. Choose OGF or EGF based on whether objects are unlabelled or labelled.
3. Translate using the dictionary: union → add, product → multiply, Seq → 1/(1−), Set → exp (EGF), Cyc → log (EGF).
4. Extract coefficients via closed forms, recurrences, or NTT-based polynomial arithmetic.
5. Asymptotics: the dominant singularity of the GF determines the exponential growth rate via transfer theorems.
6. In CP, recognise when a counting problem has a natural symbolic decomposition — the GF then gives you the solution structure (and often, an efficient algorithm via NTT).