AIOJ

In combinatorics, graph enumeration (Graph Enumeration) is the branch of combinatorics concerned with counting graphs satisfying specified properties. Generating functions, the Pólya enumeration theorem, the symbolic method, and OEIS are among the most important tools for these problems. Graph enumeration is divided into labeled and unlabeled problems. In most cases¹, labeled problems are simpler than their unlabeled counterparts, so we begin with labeled graphs.

Labeled Trees

This is Cayley's formula; see the Prüfer sequence. We can also use Kirchhoff's matrix-tree theorem, generating functions, and Lagrange's theorem to obtain the same result.

Exercises

Hihocoder 1047. Random Tree

Labeled Connected Graphs

Example: POJ 1737, Connected Graph

Problem statement: count the number of labeled connected graphs on $n$ vertices ( $n \leq 50$ ).

This type of problem first appeared in Lou Zhiming's Manba Eight Problems series. Let $g_n$ be the number of labeled graphs on $n$ vertices, and let $c_n$ be the sequence to be found. A graph on $n$ vertices has at most $\binom{n}{2}$ edges; each edge has two independent states, present or absent, so $g_n = 2^{\binom{n}{2}}$ . Fix one vertex and enumerate the size of its connected component. We then choose $i-1$ of the remaining $n-1$ vertices to form a connected component. Vertices outside that component may be joined arbitrarily, giving the following recurrence:

\begin{align} \sum_{i=1}^{n} \binom{n-1}{i-1} c_i g_{n-i} &= g_n \\ c_n &= g_n - \sum_{i=1}^{n-1} \binom{n-1}{i-1} c_i g_{n-i} \end{align}

Rearranging gives an $O(n^2)$ recurrence for the sequence $c_n$ , which solves the problem.

Example: CTSC 2013, Urban Planning

Problem statement: count the number of labeled connected graphs on $n$ vertices ( $n \leq 130000$ ).

For sequence problems with larger limits, we usually construct generating functions for the sequences so that efficient polynomial algorithms can be used.

Method 1: Divide-and-Conquer FFT

The recurrence above can be viewed as a self-convolution, so it can be computed with divide-and-conquer FFT in $O(n\log^2n)$ time.

Method 2: Polynomial Inversion

Expand the binomial coefficients in the recurrence above and transform it:

\begin{align} \sum_{i=1}^{n} \binom{n-1}{i-1} c_i g_{n-i} &= g_n \\ \sum_{i=1}^{n} \frac{c_i}{(i-1)!} \frac{g_{n-i}}{(n-i)!} &= \frac{g_n}{(n-1)!} \end{align}

Construct the polynomials:

\begin{align} C(x) &= \sum_{n=1} \frac{c_n}{(n-1)!} x^n \\ G(x) &= \sum_{n=0} \frac{g_n}{n!} x^n \\ H(x) &= \sum_{n=1} \frac{g_n}{(n-1)!} x^n \end{align}

Substitution into the equation above gives $CG = H$ . Use polynomial inversion and then convolution to solve for $C(x)$ .

Method 3: Polynomial exp

Another approach is to use the combinatorial meaning of polynomial exp in EGFs. Let $C(x)$ and $G(x)$ be the EGFs of labeled connected graphs and simple graphs, respectively. Then:

\begin{align} \exp(C(x)) &= G(x) \\ C(x) &= \ln(G(x)) \end{align}

Use polynomial ln to solve for $C(x)$ .

Labeled Eulerian and Bipartite Graphs

Example: SPOJ KPGRAPHS, Counting Graphs

Problem statement: count the number of labeled graphs on $n$ vertices satisfying each of the following properties ( $n \leq 1000$ ).

Connected graphs A001187.
Eulerian graphs A033678.
Bipartite graphs A047864.

The code length is limited in this problem, so a polynomial template cannot be used directly; generating functions can still help us analyze it.

The connected-graph problem was solved in the previous example; now consider Eulerian graphs. The methods above for counting connected graphs can all be generalized to labeled connected graphs satisfying an arbitrary property. For example, replace $g_n$ in the connected-graph recurrence, which counts arbitrary graphs, with the number of graphs whose vertex degrees are all even. The resulting $c_n$ counts Eulerian graphs.

We encapsulate the recurrence from POJ 1737 as a connected-component function:

void ln(Int C[], Int G[]) {
  for (int i = 1; i <= n; ++i) {
    C[i] = G[i];
    for (int j = 1; j <= i - 1; ++j)
      C[i] -= binom[i - 1][j - 1] * C[j] * G[i - j];
  }
}

The first two questions are then easy to solve:

for (int i = 1; i <= n; ++i) G[i] = pow(2, binom[i][2]);
ln(C, G);
for (int i = 1; i <= n; ++i) G[i] = pow(2, binom[i - 1][2]);
ln(E, G);

The connected-component recurrence here is equivalent to taking the polynomial ln of its EGF. Similarly, we can write an inverse connected-component function, which is equivalent to taking the polynomial exp of its EGF.

void exp(Int G[], Int C[]) {
  for (int i = 1; i <= n; ++i) {
    G[i] = C[i];
    for (int j = 1; j <= i - 1; ++j)
      G[i] += binom[i - 1][j - 1] * C[j] * G[i - j];
  }
}

We next discuss counting labeled bipartite graphs.

Let $b_n$ denote the number of bipartite graphs on $n$ vertices, and let $g_n$ denote the number of ways to 2-color the vertices of an n-vertex graph so that no edge joins vertices of the same color. Enumerating the number of vertices of one color gives²:

g_n = \sum_{i=0}^{n} \binom{n}{i}2^{i(n-i)}

We next establish the relationship between $g_n$ and $b_n$ in two different ways.

Method 1: Count Twice

Let $c_{n, k}$ denote the number of bipartite graphs with k connected components. We readily obtain:

\begin{align} b_n &= \sum_{i=1}^{n} c_{n, i} \\ g_n &= \sum_{i=1}^{n} c_{n, i} 2^i \end{align}

Comparing the two expressions for $g_n$ and expanding gives:

\begin{align} \sum_{i=0}^{n} \binom{n}{i}2^{i(n-i)} &= \sum_{i=1}^{n} c_{n, i} 2^i \\ c_{n, i} &= \sum_{i=0}{n-1} \binom{n-1}{i-1} c_{n, 1}c_{n-i,k-1} \end{align}

It follows that the recurrence for $b_n$ has complexity $O(n^3)$ . Applying inclusion-exclusion further reduces it to $O(n^2)$ , enough to solve the problem.

Method 2: Connected-Component Recurrence

Methods 2 and 3 both use the connected bipartite graph sequence $b1_n$ A001832 to connect $g_n$ and $b_n$ .

Every connected bipartite graph has exactly two distinct 2-colorings, corresponding to two connected 2-colored graphs. Therefore, applying connected-component decomposition to $g_n$ produces exactly twice the sequence $b1_n$ , while $b_n$ is obtained from $b1_n$ by inverse connected-component decomposition.

Therefore:

for (int i = 1; i <= n; ++i) {
  G[i] = 0;
  for (int j = 0; j < i + 1; ++j) G[i] += binom[i][j] * pow(2, j * (i - j));
}
ln(B1, G);
for (int i = 1; i <= n; ++i) B1[i] /= 2;
exp(B, B1);

Both recurrences have complexity $O(n^2)$ , so either solves the problem.

Method 3: Polynomial exp

We can also use EGFs to understand the recurrence above.

Let $G(x)$ , $B1(x)$ , and $B(x)$ be the EGFs of $g_n$ , $b1_n$ , and $b_n$ , respectively. Applying Method 2 gives:

\begin{align} G(x) &= \exp(2B1(x)) \\ B(x) &= \exp(B1(x)) \\ &= \exp(\frac{\ln{G(x)}}{2}) \\ &= \sqrt{G} \end{align}

Differentiate both sides of the equation and compare coefficients to obtain an easy-to-code recurrence that solves the problem. Methods 2 and 3 are essentially the same, and Method 3 generally has better time complexity.

\begin{align} B_n^2 &= G \\ 2B_nB_n' &= G' \end{align}

Reference code

#include <iostream>
using namespace std;

using LL = long long;
constexpr int MOD = int(1e9) + 7;

// <<= '2. Number Theory .,//{
namespace NT {
void INC(int& a, int b) {
  a += b;
  if (a >= MOD) a -= MOD;
}

int sum(int a, int b) {
  a += b;
  if (a >= MOD) a -= MOD;
  return a;
}

void DEC(int& a, int b) {
  a -= b;
  if (a < 0) a += MOD;
}

int dff(int a, int b) {
  a -= b;
  if (a < 0) a += MOD;
  return a;
}

void MUL(int& a, int b) { a = (LL)a * b % MOD; }

int pdt(int a, int b) { return (LL)a * b % MOD; }

int _I(int b) {
  int a = MOD, x1 = 0, x2 = 1, q;
  while (1) {
    q = a / b, a %= b;
    if (!a) return x2;
    DEC(x1, pdt(q, x2));

    q = b / a, b %= a;
    if (!b) return x1;
    DEC(x2, pdt(q, x1));
  }
}

void DIV(int& a, int b) { MUL(a, _I(b)); }

int qtt(int a, int b) { return pdt(a, _I(b)); }

int pow(int a, LL b) {
  int c(1);
  while (b) {
    if (b & 1) MUL(c, a);
    MUL(a, a), b >>= 1;
  }
  return c;
}

template <class T>
T pow(T a, LL b) {
  T c(1);
  while (b) {
    if (b & 1) c *= a;
    a *= a, b >>= 1;
  }
  return c;
}

template <class T>
T pow(T a, int b) {
  return pow(a, (LL)b);
}

struct Int {
  int val;

  operator int() const { return val; }

  Int(int _val = 0) : val(_val) {
    val %= MOD;
    if (val < 0) val += MOD;
  }

  Int(LL _val) : val(_val) {
    _val %= MOD;
    if (_val < 0) _val += MOD;
    val = _val;
  }

  Int& operator+=(const int& rhs) {
    INC(val, rhs);
    return *this;
  }

  Int operator+(const int& rhs) const { return sum(val, rhs); }

  Int& operator-=(const int& rhs) {
    DEC(val, rhs);
    return *this;
  }

  Int operator-(const int& rhs) const { return dff(val, rhs); }

  Int& operator*=(const int& rhs) {
    MUL(val, rhs);
    return *this;
  }

  Int operator*(const int& rhs) const { return pdt(val, rhs); }

  Int& operator/=(const int& rhs) {
    DIV(val, rhs);
    return *this;
  }

  Int operator/(const int& rhs) const { return qtt(val, rhs); }

  Int operator-() const { return MOD - *this; }
};

}  // namespace NT

using namespace NT;

constexpr int N = int(1e3) + 9;
Int binom[N][N], C[N], E[N], B[N], B1[N], G[N];
int n;

void ln(Int C[], Int G[]) {
  for (int i = 1; i <= n; ++i) {
    C[i] = G[i];
    for (int j = 1; j <= i - 1; ++j)
      C[i] -= binom[i - 1][j - 1] * C[j] * G[i - j];
  }
}

void exp(Int G[], Int C[]) {
  for (int i = 1; i <= n; ++i) {
    G[i] = C[i];
    for (int j = 1; j <= i - 1; ++j)
      G[i] += binom[i - 1][j - 1] * C[j] * G[i - j];
  }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);

  n = 1000;
  for (int i = 0; i < n + 1; ++i) {
    binom[i][0] = 1;
    for (int j = 0; j < i; ++j)
      binom[i][j + 1] = binom[i - 1][j] + binom[i - 1][j + 1];
  }

  for (int i = 1; i <= n; ++i) G[i] = pow(2, binom[i][2]);
  ln(C, G);
  for (int i = 1; i <= n; ++i) G[i] = pow(2, binom[i - 1][2]);
  ln(E, G);
  for (int i = 1; i <= n; ++i) {
    G[i] = 0;
    for (int j = 0; j < i + 1; ++j) G[i] += binom[i][j] * pow(2, j * (i - j));
  }
  ln(B1, G);
  for (int i = 1; i <= n; ++i) B1[i] /= 2;
  exp(B, B1);

  int T;
  cin >> T;
  while (T--) {
    cin >> n;
    cout << "Connected: " << C[n] << '\n'
         << "Eulerian: " << E[n] << '\n'
         << "Bipartite: " << B[n] << "\n\n";
  }
}

Exercises

Riddell's Formula

The use of exp for EGFs above is sometimes called Riddell's formula for labeled graphs. The Euler transform of generating functions is also sometimes called Riddell's formula for unlabeled graphs. The latter first appeared in Euler's study of partition numbers; besides graph enumeration, it also appears in the complete-knapsack problem.

For a given sequence $a_i$ and its corresponding OGF $A(x)$ , define the Euler transform of $A(x)$ as:

\begin{align} \mathcal{E}(A(x)) &= \prod_{i} (1-x^i)^{-a_i} \\ &= \exp (\sum_{i} \frac{A(x^i)}{i}) \end{align}

Suppose the coefficients of $\mathcal{E}(A(x))$ are $b_i$ . Define the auxiliary array $c_i = \sum_{d|n} d a_d$ . Then:

n b_n = c_n + \sum_{i=1}^{n-1} c_i b_{n-i}

Unlabeled Trees

Example: SPOJ PT07D, Let us count 1 2 3

Problem statement: count the number of trees on n vertices satisfying each of the following properties.

Labeled rooted trees A000169.
Labeled unrooted trees A000272.
Unlabeled rooted trees A000081.
Unlabeled unrooted trees A000055.

Rooted Trees

The labeled case was handled earlier. Now consider unlabeled rooted trees. Let their OGF be $F(x)$ . Applying the Euler transform gives:

F(x) = x\mathcal{E}(F(x))

Extract the coefficients.

Unrooted Trees

Use inclusion-exclusion: subtract the rooted-tree configurations whose root is not a centroid from all rooted-tree configurations, and discuss the parity of $n$ .

When $n$ is odd:

There must be a subtree of size $\geq \left\lceil \frac{n}{2}\right\rceil$ ; enumerating its size gives:

g_n = f_n - \sum_{i=\left\lceil\frac{n}{2}\right\rceil}^{n-1} f_i f_{n-i}

When $n$ is even:

When there are two centroids, the preceding process subtracts the tree only once, so we must subtract an additional term:

g_n = f_n - \sum_{i=\frac{n}{2}+1}^{n-1} f_i f_{n-i} - \binom{f_{\frac{n}{2}}}{2}

Example: Luogu P5900, Counting Unlabeled Unrooted Trees

Problem statement: count the number of unlabeled unrooted trees on n vertices ( $n \leq 200000$ ).

For larger limits, the same approach applies: use a polynomial template after the Euler transform.

Unlabeled Simple Graphs

Example: SGU 282, Isomorphism

Problem statement: count the number of ways to color the edges of an unlabeled complete graph on n vertices with m colors.

When m = 2, the object being counted is precisely the unlabeled simple graph A000088. Consider the Pólya enumeration theorem:

\frac{1}{|G|}\sum_{g\in G} m^{c(g)}

In this problem, the permutation group $G$ is the permutation group on the edge set induced by the symmetric group on $n$ vertices. The brute-force enumeration has size $O(n!)$ , so it cannot solve the problem.

Classify permutations by their cycle structure. Each cycle structure corresponds to a partition. We use dfs() to generate the partitions, reducing the problem to finding, for each partition $p$ , the number of corresponding permutations $w(p)$ and the number of cycles $c(p)$ in each permutation class. The answer is:

\frac{1}{|G|} \sum_{p \in P} w(p) m^{c(p)}

Consider $w(p)$ . Each partition corresponds to a cyclic arrangement, and the order of parts of equal size is irrelevant. Thus:

w(p) = \frac{n!}{\prod_{i}(p_i)\prod_{i}(q_i!)}

Here $q_i$ denotes the number of parts of size $i$ appearing in $p$ .

Now consider $c(p)$ . The cycle on the set of vertices affected by $p$ has length $|p|$ . However, the problem colors edges, so we must also examine the edge permutation induced by the vertex permutation.

If the endpoints of an edge lie in the same cycle, let that cycle have size $p_i$ . Then the number of cycles generated on edges is exactly $\left\lfloor \frac{p_i}{2} \right\rfloor$ .

If the endpoints lie in two different cycles, let their sizes be $p_i$ and $p_j$ . Every orbit has length $\operatorname{lcm}(p_i,p_j)$ , so the number of cycles generated on edges is exactly $\frac{p_i p_j}{\operatorname{lcm}(p_i,p_j)} = \gcd(p_i, p_j)$ .

Reference code

#include <iostream>
#include <vector>
using namespace std;

using LL = long long;
int MOD = int(1e9) + 7;

namespace NT {
void INC(int& a, int b) {
  a += b;
  if (a >= MOD) a -= MOD;
}

int sum(int a, int b) {
  a += b;
  if (a >= MOD) a -= MOD;
  return a;
}

void DEC(int& a, int b) {
  a -= b;
  if (a < 0) a += MOD;
}

int dff(int a, int b) {
  a -= b;
  if (a < 0) a += MOD;
  return a;
}

void MUL(int& a, int b) { a = (LL)a * b % MOD; }

int pdt(int a, int b) { return (LL)a * b % MOD; }

int _I(int b) {
  int a = MOD, x1 = 0, x2 = 1, q;
  while (1) {
    q = a / b, a %= b;
    if (!a) return x2;
    DEC(x1, pdt(q, x2));

    q = b / a, b %= a;
    if (!b) return x1;
    DEC(x2, pdt(q, x1));
  }
}

void DIV(int& a, int b) { MUL(a, _I(b)); }

int qtt(int a, int b) { return pdt(a, _I(b)); }

int pow(int a, LL b) {
  int c(1);
  while (b) {
    if (b & 1) MUL(c, a);
    MUL(a, a), b >>= 1;
  }
  return c;
}

template <class T>
T pow(T a, LL b) {
  T c(1);
  while (b) {
    if (b & 1) c *= a;
    a *= a, b >>= 1;
  }
  return c;
}

template <class T>
T pow(T a, int b) {
  return pow(a, (LL)b);
}

struct Int {
  int val;

  operator int() const { return val; }

  Int(int _val = 0) : val(_val) {
    val %= MOD;
    if (val < 0) val += MOD;
  }

  Int(LL _val) : val(_val) {
    _val %= MOD;
    if (_val < 0) _val += MOD;
    val = _val;
  }

  Int& operator+=(const int& rhs) {
    INC(val, rhs);
    return *this;
  }

  Int operator+(const int& rhs) const { return sum(val, rhs); }

  Int& operator-=(const int& rhs) {
    DEC(val, rhs);
    return *this;
  }

  Int operator-(const int& rhs) const { return dff(val, rhs); }

  Int& operator*=(const int& rhs) {
    MUL(val, rhs);
    return *this;
  }

  Int operator*(const int& rhs) const { return pdt(val, rhs); }

  Int& operator/=(const int& rhs) {
    DIV(val, rhs);
    return *this;
  }

  Int operator/(const int& rhs) const { return qtt(val, rhs); }

  Int operator-() const { return MOD - *this; }
};

}  // namespace NT

using namespace NT;

constexpr int N = int(5e1) + 9;
Int Fact[N];
vector<vector<int>> Partition;
vector<int> cur;
int n, m;

void gen(int n = ::n, int s = 1) {
  if (!n) {
    Partition.push_back(cur);
  } else if (n >= s) {
    cur.push_back(s);
    gen(n - s, s);
    cur.pop_back();
    gen(n, s + 1);
  }
}

Int w(const vector<int> P) {
  Int z = Fact[n];
  int c = 0, l = P.front();

  for (auto p : P) {
    z /= p;
    if (p != l) {
      z /= Fact[c];
      l = p;
      c = 1;
    } else {
      ++c;
    }
  }

  z /= Fact[c];
  return z;
}

int gcd(int x, int y) { return y ? gcd(y, x % y) : x; }

int c(const vector<int> P) {
  int z = 0;
  for (int i = 0; i < P.size(); ++i) {
    z += P[i] / 2;
    for (int j = 0; j < i; ++j) z += gcd(P[i], P[j]);
  }
  return z;
}

int main() {
  cin >> n >> m >> MOD;
  Fact[0] = 1;
  for (int i = 1; i <= n; ++i) Fact[i] = Fact[i - 1] * i;

  gen();

  Int res = 0;
  for (auto P : Partition) {
    res += w(P) * pow(m, c(P));
  }
  res /= Fact[n];
  cout << res << endl;
}

Exercises

References and notes

Footnotes

Perhaps unlabeled binary trees are a counterexample: when the structure is simple, the corresponding permutation group is the identity group (Identity Group), so the labeled version can be obtained directly by multiplying by $n!$ . ↩
PinkRabbit's blog notes that this sequence can also be optimized with the Chirp Z-Transform. ↩