Combinatorial Species — Species Theory Overview

June 2026 · 28 min read

What Is a Combinatorial Species?

In 1981, André Joyal introduced the theory of combinatorial species to give a rigorous, categorical foundation to the art of counting combinatorial structures. The central question species theory answers is: What does it mean for a combinatorial structure to be “the same kind of thing” as another?

Formally, a species of structures F is a functor from the category B of finite sets with bijections to itself. That is, for every finite set U, the species assigns a finite set F[U] of F-structures on U, and for every bijection σ: U → V, it assigns a function F[σ]: F[U] → F[V] that “transports” structures from U to V.

Functoriality Axioms

The functor must satisfy two properties:

1. Identity: F[id_U] = id_F[U]. Doing nothing to the labels does nothing to the structures.
2. Composition: F[σ ˆ τ] = F[σ] ˆ F[τ]. Relabeling in two steps is the same as relabeling all at once.

Key Examples

Consider the label set U = {1, 2, 3}. Here are some classic species evaluated on it:

• Species of linear orders (L): L[{1,2,3}] = {(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)} — all 3! = 6 permutations.
• Species of sets (E): E[{1,2,3}] = {{1,2,3}} — exactly one structure, the set itself.
• Species of graphs (G): G[{1,2,3}] contains all 2^C(3,2) = 8 labelled graphs on three vertices.
• Species of trees (A): A[{1,2,3}] contains all 3 labelled trees on three vertices (by Cayley’s formula, nⁿ⁻² = 3).

The power of species theory is that it provides algebraic operations (sum, product, composition, differentiation) that let us build complex species from simple ones — and these operations translate directly into operations on generating functions.

Basic Species and Their Series

Every species F has two fundamental generating series that encode the counts |F[n]| (the number of F-structures on a set of size n):

• Type generating series (TGS / OGF-like): F̃(x) = Σn≥0 f̃n xn, where f̃_n counts the number of isomorphism types (unlabelled structures) of size n.
• Exponential generating series (EGS / EGF): F(x) = Σn≥0 |F[n]| · xn/n!, counting labelled structures.

Table of Elementary Species

Deriving the EGF for E (Sets)

For the species of sets, |E[n]| = 1 for every n (there is exactly one “set structure” on any label set). Therefore:

E(x) = Σn≥0 1 · xn/n! = ex

Deriving the EGF for L (Linear Orders)

|L[n]| = n! (every permutation is a distinct linear order). So:

L(x) = Σn≥0 n! · xn/n! = Σn≥0 xn = 1/(1−x)

Deriving the EGF for C (Cycles)

|C[n]| = (n−1)! for n ≥ 1 (cyclic permutations). So:

C(x) = Σn≥1 (n−1)! · xn/n!
     = Σn≥1 xn/n
     = ln(1/(1−x))

Operations on Species

The algebraic beauty of species theory emerges from four fundamental operations. Each one has a precise combinatorial meaning and a direct translation into generating functions.

Sum: F + G

An (F + G)-structure on U is either an F-structure or a G-structure on U (disjoint union). In terms of EGFs:

(F + G)(x) = F(x) + G(x)

Example: The species of “graphs that are either a tree or a cycle” has EGF equal to A(x) + C(x).

Product: F · G

An (F · G)-structure on U is a partition of U into two disjoint subsets U₁, U₂ together with an F-structure on U₁ and a G-structure on U₂. The EGF uses the exponential convolution (Cauchy product for EGFs):

(F · G)(x) = F(x) · G(x)

This works because the binomial coefficient C(n, k) that counts ways to split labels is already “baked into” the EGF multiplication formula.

Composition: F ˆ G

An (F ˆ G)-structure on U is a partition of U into non-empty blocks, a G-structure on each block, and an F-structure on the set of blocks. The EGF satisfies:

(F ˆ G)(x) = F(G(x))    (provided G(0) = 0)

This is the substitution principle for EGFs, and it is spectacularly powerful. Classic applications:

• Set partitions: E ˆ E₊, where E₊ is the species of non-empty sets. EGF: exp(e^x − 1). Coefficients give Bell numbers.
• Permutations as sets of cycles: S = E ˆ C. EGF: exp(ln(1/(1−x))) = 1/(1−x). ✓
• Labelled graphs with connected components: G = E ˆ C_G, where C_G is connected graphs.

Derivative: F′

The derivative of a species F is defined by F′[U] = F[U ∪ {☆}], where ☆ is a distinguished new element. Informally: an F′-structure is an F-structure with one extra label that is “pointed out” (rooted). The EGF satisfies:

F′(x) = d/dx F(x)

Example: L′ = L · L (a linear order with a marked element is two linear orders — the part before and after the mark). Check: d/dx [1/(1−x)] = 1/(1−x)² = L(x) · L(x). ✓

Operations Summary

The Dissymmetry Theorem for Trees

One of the most celebrated applications of species theory is a clean derivation of Cayley’s formula: the number of labelled trees on n vertices is nⁿ⁻². Species theory provides not just a proof but a structural explanation of why this formula holds.

The Species Equation for Rooted Trees

Let A denote the species of rooted labelled trees. A rooted tree is either a single root with no children, or a root whose children are themselves the roots of an unordered set of rooted subtrees. This gives the recursive species equation:

A = X · E(A)

In terms of EGFs, if a(x) denotes the EGF of rooted labelled trees:

a(x) = x · exp(a(x))

By Lagrange inversion, [xⁿ] a(x) = nⁿ⁻¹/n!, so the number of rooted labelled trees on n vertices is nⁿ⁻¹.

From Rooted to Unrooted: Dissymmetry

The dissymmetry theorem relates rooted and unrooted trees via edge-rooted trees. Let a denote the species of unrooted trees, A rooted trees, and A_e edge-rooted trees (a tree with a distinguished edge). Then:

a + Ae = A + (A unordered pair of rooted at endpoints)

This combinatorial identity, after careful bookkeeping, yields the unrooted count. For labelled trees: dividing rooted count nⁿ⁻¹ by n (each unrooted tree has n root choices) gives nⁿ⁻². Cayley’s formula follows.

The Implicit Species Theorem

The equation A = X · E(A) is an example of an implicit species equation: the species is defined in terms of itself. Joyal’s implicit species theorem guarantees that such equations have unique solutions under mild conditions (the “admissibility” criterion). This is the species-theoretic counterpart of the Lagrange inversion formula for formal power series.

Cycle Index Series

The EGF captures labelled counting, and the TGS captures unlabelled counting. The cycle index series Z_F is a more refined invariant that encodes both and more.

Definition

For a species F, the cycle index series is a formal power series in infinitely many variables p₁, p₂, p₃, … :

ZF(p1, p2, ...) = Σn≥0 (1/n!) Σσ∈Sn |FixF[n](σ)| · p1σ1 p2σ2 ···

where σ_k denotes the number of k-cycles in the permutation σ, and Fix_F[n](σ) is the set of F-structures fixed by the relabeling σ.

Recovering EGF and TGS

• EGF: substitute p_k = x^k for all k into Z_F. Actually, the simpler route: set p₁ = x, p_k = 0 for k ≥ 2. This selects only the identity permutation, recovering the labelled count. More precisely: F(x) = Z_F(x, 0, 0, …) · (correction factors). The standard identity is F(x) = Z_F(x, x², x³, …) gives the TGS.
• TGS: F̃(x) = Z_F(x, x², x³, …). This is exactly Pólya substitution.

Connection to Pólya Enumeration

Pólya’s enumeration theorem is a special case of the cycle index machinery. The cycle index of a permutation group G acting on a set of slots is:

ZG(p1, ..., pn) = (1/|G|) Σg∈G p1c1(g) p2c2(g) ··· pncn(g)

Substituting p_k = (number of colours)^k gives Burnside/Pólya counting. Species theory unifies this with the labelled world, viewing Pólya as the “unlabelled projection” of a richer structure.

Cycle Index of Elementary Species

C++ Applications

Species theory guides the derivation of generating-function equations. Once we have the GF, competitive-programming implementation reduces to polynomial coefficient extraction — typically via NTT-based polynomial operations or direct recurrence.

1. Cayley’s Formula Verification (Rooted Trees)

The species equation A = X · E(A) gives a(x) = x e^a(x). By Lagrange inversion the coefficient of xⁿ in a(x) is nⁿ⁻¹/n!. Below we verify this by computing the coefficients of a(x) iteratively using the recurrence derived from Newton’s method on the implicit equation.

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

const int MOD = 998244353;

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

long long inv(long long a, long long mod) {
    return power(a, mod - 2, mod);
}

// Compute [x^n] a(x) where a(x) = x * exp(a(x)).
// By Lagrange inversion: n! * [x^n] a(x) = n^{n-1}.
// This function returns the number of rooted labelled trees on n nodes.
long long rooted_trees(int n) {
    if (n == 0) return 0;
    return power(n, n - 1, MOD);
}

// Verify Cayley's formula: unrooted labelled trees = n^{n-2}.
long long cayley(int n) {
    if (n <= 2) return 1;
    return power(n, n - 2, MOD);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    cout << "Rooted labelled trees on " << n << " nodes: "
         << rooted_trees(n) << "\n";
    cout << "Unrooted labelled trees (Cayley): "
         << cayley(n) << "\n";

    return 0;
}

2. Bell Numbers via Species Composition

Set partitions = E ˆ E₊, so the EGF is exp(e^x − 1). We compute Bell numbers B(n) = n! [xⁿ] exp(e^x−1) using the Bell triangle recurrence, which is ultimately a consequence of the species decomposition.

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

const int MOD = 998244353;

// Bell numbers via the Bell triangle.
// B(0) = 1, and the triangle is built row by row:
//   T[0][0] = 1
//   T[i][0] = T[i-1][i-1]
//   T[i][j] = T[i][j-1] + T[i-1][j-1]
// B(n) = T[n][0].
vector<long long> bell_numbers(int maxn) {
    vector<long long> B(maxn + 1);
    vector<long long> prev(maxn + 1), curr(maxn + 1);

    prev[0] = 1;
    B[0] = 1;

    for (int i = 1; i <= maxn; i++) {
        curr[0] = prev[i - 1];
        for (int j = 1; j <= i; j++) {
            curr[j] = (curr[j - 1] + prev[j - 1]) % MOD;
        }
        B[i] = curr[0];
        swap(prev, curr);
    }

    return B;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

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

    return 0;
}

3. Counting Permutations by Cycle Type

The species equation S = E ˆ C tells us permutations decompose into an unordered collection of cycles. If we want to count permutations of [n] with exactly k cycles, these are the unsigned Stirling numbers of the first kind |s(n,k)|. We compute them via the recurrence |s(n,k)| = (n−1) · |s(n−1,k)| + |s(n−1,k−1)|.

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

const int MOD = 998244353;

// Unsigned Stirling numbers of the first kind.
// |s(n,k)| = number of permutations of [n] with exactly k cycles.
// Recurrence: |s(n,k)| = (n-1)*|s(n-1,k)| + |s(n-1,k-1)|.
vector<vector<long long>> stirling1(int maxn) {
    vector<vector<long long>> s(maxn + 1, vector<long long>(maxn + 1, 0));
    s[0][0] = 1;
    for (int n = 1; n <= maxn; n++) {
        for (int k = 1; k <= n; k++) {
            s[n][k] = ((long long)(n - 1) * s[n - 1][k] % MOD
                       + s[n - 1][k - 1]) % MOD;
        }
    }
    return s;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    auto s = stirling1(n);
    for (int k = 1; k <= n; k++) {
        cout << "|s(" << n << "," << k << ")| = "
             << s[n][k] << "\n";
    }

    // Total permutations = sum over k of |s(n,k)| should be n!
    long long total = 0;
    for (int k = 1; k <= n; k++)
        total = (total + s[n][k]) % MOD;
    cout << "Total permutations: " << total << "\n";

    return 0;
}

CP Relevance

Species theory is not a “competitive-programming algorithm” you implement directly. Rather, it is a thinking tool — a systematic way to decompose a counting problem into simpler pieces, translate the decomposition into a generating function, and then extract coefficients efficiently.

Pattern: Recursive Decomposition

Many CP counting problems have a recursive flavour: a structure of size n is built from smaller pieces. Species equations capture this exactly:

• Rooted trees: A = X · E(A) ⇒ a(x) = x e^a(x)
• Binary trees: B = 1 + X · B · B ⇒ b(x) = 1 + x b(x)²
• Connected graphs from all graphs: G = E ˆ C_G ⇒ c(x) = ln(g(x))
• Set partitions: P = E ˆ E₊ ⇒ p(x) = exp(e^x−1)

Once you have the GF equation, coefficient extraction is mechanical: Lagrange inversion, Newton’s method for polynomial composition, or direct recurrence.

Pattern: Unlabelled Counting via Cycle Index

Unlabelled counting problems (e.g., “count non-isomorphic graphs”) are notoriously hard in general. But when the structure has a species description, the cycle index series gives a systematic way to enumerate isomorphism types. This connects to Pólya enumeration, which we covered in the earlier module posts.

Pattern: Converting to Polynomial Recurrences

The key CP trick is: derive the GF equation from species reasoning, then differentiate or manipulate it to get a recurrence for the coefficients. For example:

1. From a(x) = x · exp(a(x)), differentiate both sides.
2. Get a′(x) = exp(a(x)) + x · exp(a(x)) · a′(x) = (a(x)/x) · (1 + x · a′(x)).
3. Equate coefficients to get a recurrence for the n-th coefficient in terms of previous ones.
4. Implement the recurrence in O(n²) or, with NTT tricks, O(n log n).

When Species Thinking Helps in Contests

Summary

1. A combinatorial species is a functor from finite sets (with bijections) to finite sets — a rule that places structures on labels, compatible with relabeling.
2. Elementary species (0, 1, X, E, L, C, S) form the building blocks. Each has known EGF and TGS.
3. Sum, product, composition, derivative translate to addition, multiplication, substitution, and differentiation of EGFs.
4. The implicit species theorem (+ Lagrange inversion) handles recursive species equations like A = X · E(A) for rooted trees.
5. The dissymmetry theorem connects rooted and unrooted tree counts, yielding Cayley’s formula.
6. The cycle index series generalises the EGF, unifying labelled and unlabelled counting. Pólya enumeration is a special case.
7. In CP, species theory is a derivation tool: identify the species decomposition, translate to a GF equation, extract coefficients via recurrence or polynomial operations.