一些简单的图计数问题

---

老年健忘选手终于下定决心去学数数了.

综述

大概是利用生成函数推出一些式子, 然后拿多项式去算吧 = =

前置知识

1. 多项式的相关运算

   最好有跑地比谁都快的板子, 以免在做题的时候被卡常.

2. 生成函数

   对于一个数列 $\{ a_n \}$, 有

   $\{ a_n \}$ 的普通生成函数 (Ordinary Generating Function, OGF), 为

   $$g(x) = \sum\limits_{k = 0}^\infty a_k x^k$$

   常用于处理无标号计数问题.

   $\{ a_n \}$ 的指数生成函数, (Exponential Generating Function, EGF), 为

   $$g(x) = \sum\limits_{k = 0}^\infty a_k \frac{x^k}{k!}$$

   常用于处理有标号计数问题.

   $\{ a_n \}$ 的组合生成函数, 为

   $$g(x) = \sum\limits_{k = 0}^\infty a_k \frac{x^k}{2 ^ \binom{k}{2} k!}$$

   其中 “组合生成函数” 是从 JOHNKRAM 课件里看来的新东西, 似乎只在有标号有向图计数中用到过…

3. 拉格朗日反演

   在遇到多项式复合逆的时候快速计算出某一位的值. 如果要计算多个位的值, 可考虑分块. 详见 Luogu P5809 【模板】多项式复合逆.

   设多项式 $F(x), G(x)$ 满足 $F(G(x)) = G(F(x)) = x$, 并记 $[x^n]F(x)$ 表示 $F(x)$ 的第 $n$ 次项系数, 那么

   $$[x^n] G(x) = \frac{1}{n} [x^{n-1}] \left(\frac{x}{F(x)}\right)^n$$

   还有一个拓展形式. 设 $H(x)$ 是另一个多项式, 那么

   $$[x^n] H\left(G(x)\right) = \frac{1}{n} [x^{n-1}] H'(x) \left(\frac{x}{F(x)}\right)^n$$

连通 / 不连通?

对于有标号元素 $A$ 组成的集合 $B$, 不妨设 $A$ 的 EGF 为 $A(x)$. 考虑到集合内的元素没有顺序关系, 可以得到 $B$ 的 EGF 为

$$B(x) = \sum_{k = 0} ^ \infty \frac{A(x) ^ k}{k!} = \exp A(x)$$

应用在图计数中, 可以将非连通图看作多个连通图构成的集合.

也就是在确定连通图个数的 EGF 后, 可以通过多项式 $\exp$ 得出非连通图个数的 EGF.

有标号无向图计数

树

考虑到 Prufer 序列将一个带标号且有 $n$ 个节点的树用 $[1, n]$ 中 $n-2$ 个整数表示, 且 Prufer 序列同树一一对应. 那么, 直接统计 Prufer 序列的个数即可.

记树的 EGF 为 $T(x)$, 那么

$$T(x) = \sum_{k = 2} ^ \infty \frac{k ^ {k - 2}}{k!} x^k$$

此时得到是无根树的结果, 而对于有根树, 枚举根的位置计算即可, 也就是无根树的个数乘以点数.

无向图

对于含有 $n$ 个点的无向图, 先考虑不连通的情况, 直接利用 $\binom{n}{2}$ 条边的存在情况计算即可.

记无向图的 EGF 为 $G(x)$, 那么

$$G(x) = \sum_{k = 0} ^ \infty \frac{2 ^ \binom{n}{2}}{k!} x ^ k$$

根据之前的讨论, 无向连通图的 EGF 即为 $\exp G(x)$.

例题

• Luogu P4841 城市规划

基环树

基环树即为包含 $n$ 个节点, $n$ 条边的简单图. 在形态上仅有一个简单环, 且环上每一个节点都是一棵有根树的根节点.

回忆有标号环的计数, 以及圆排列公式. 对于组合对象 $A$, 由 $A$ 构成的环 $B$ 的 EGF 为

$$B(x) = \sum_{k = 1} ^ \infty \frac{(k - 1)!}{k!} A(x) ^ k = \sum_{k = 1} ^ \infty \frac{1}{k} A(x) ^ k = - \ln \left(1 - A(x)\right)$$

注意到基环树上一定存在一个长度 $\ge 3$ 的环, 记有根树的 EGF 为 $T(x)$, 基环树的 EGF 为 $C(x)$, 那么

$$T(x) = \sum_{k = 1} ^ \infty \frac{k ^ {k - 1}}{k!} x^k$$

考虑到基环树中的环没有方向, 可以翻转, 直接套用上面的公式会算重.

$$C(x) = \frac{1}{2} \sum_{k = 3} ^ \infty \frac{T(x) ^ k}{k}$$

化简之后可得

$$C(x) = \frac{1}{2} \ln \big(1 - T(x)\big) - \frac{1}{2} T(x) - \frac{1}{4} T(x) ^ 2$$

利用多项式 $\ln$ 和多项式乘法即可在 $O(n\log n)$ 的时间复杂度内计算.

仙人掌

如果一个无向连通图任意一条边最多属于一个简单环, 那么称这个无向连通图为仙人掌.

先钦定仙人掌上某一点为根, 设 “有根仙人掌” 个数的 EGF 为 $C(x)$, 最后在结果的系数上除 $n$ 即可.

从 “任意一条边最多属于一个简单环” 这一条件入手. 考虑根节点连出的边, 可以分为简单环上和不属于任何简单环的独立边两种.

对于环上的边, 设环中点数为 $k + 1$, 考虑环上每一个节点都可以作为有根仙人掌的根, 那么环的生成函数为 $\frac{1}{2} C(x) ^ k$. 对于独立边, 另一端点为有根仙人掌的根, 其生成函数为 $C(x)$.

而根节点连出的边可看作上述两种情况构成的集合, 同时考虑根节点的影响, 可以得出

$$C(x) = x \exp\left( C(x) + \frac{1}{2} \sum_{k = 2} ^ \infty C(x) ^ k\right) = x \exp \frac{2C(x) - C(x) ^ 2}{2 - 2 C(x)}$$

此处也可以从圆方树的角度考虑, 可以得到同样的结果. 详见: https://blog.csdn.net/qq_39972971/article/details/89214832

然后套牛顿迭代的式子, 记 $C_0(x)$ 为模 $x ^ {\lceil \frac{n}{2} \rceil}$ 意义下的结果, $C(x)$ 为模 $x ^ n$ 意义下的结果, 同时记录 $T(x)$ 来便于表述, 有

$$T(x) = x \exp \frac{ 2C_0(x) - C_0 (x) ^ 2 }{ 2 - 2 C_0(x) ^ 2 }$$ $$C(x) = C_0(x) - \frac{ 2T(x) - 2 C_0 }{ \Big( 1 + 1\ /\ \big(C_0(x) ^ 2 - 2C_0(x) + 1\big) \Big) T(x) - 2 }$$

详细的过程可以在 memset0 的博客 内找到.

至此我们得出了在 $O(n\log n)$ 的时间复杂度内计算 $n$ 项的做法. 实现时可以合并一部分式子来避免重复计算, 以及便于实现.

例题

• LOJ #6569 仙人掌计数
• Luogu P5434 有标号荒漠计数

二分图

二分图为节点可分作两个集合, 且保证集合内部不存在边的图.

先考虑将二分图的两个部分黑白染色, 枚举黑色节点的个数 $k$, 容易得到黑白染色的二分图个数 $f_n$ 为

$$f_n = \sum_{k = 0} ^ n \binom{n}{k} 2 ^ {k (n - k)}$$

我们有 $k (n - k) = \binom{n}{2} - \binom{k}{2} - \binom{n - k}{2}$, 所以原式可化作

$$f_n = \sum_{k = 0} ^ n \frac{n!}{k! (n - k)!} 2 ^ \binom{n}{2} 2 ^ {-\binom{k}{2}} 2 ^ {-\binom{n - k}{2}}$$ $$\frac{f_n}{n!\ 2 ^ {\binom{n}{2}}} = \sum_{k = 0} ^ n \frac{1}{(n - k)!\ 2 ^ \binom{n - k}{2}} \cdot \frac{1}{k!\ 2 ^ \binom{k}{2}}$$

显然是卷积的形式, 利用 FFT 即可在 $O(n \log n)$ 的时间内计算.

接下来考虑去掉染色怎么做.

设黑白染色后的二分图 EGF 为 $F(x)$, 不染色二分图 EGF 为 $B(x)$, 连通的不染色二分图为 $C(x)$. 那么有

$$F(x) = \sum_{k = 0} ^ \infty \frac{2 ^ k C(x) ^ k}{k!} = \exp \big(2C(x)\big)$$ $$B(x) = \sum_{k = 0} ^ \infty \frac{C(x) ^ k}{k!} = \exp \big( C(x) \big)$$

容易发现 $B(x) = \sqrt {F(x)}$, 利用多项式开方即可在 $O(n \log n)$ 的时间内计算.

例题

• ZYZOJ #1191 有标号二分图计数
• COGS 2393 [HZOI 2015] 有标号的二分图计数 II
• COGS 2395 [HZOI 2015] 有标号的二分图计数 III

边双连通图

边双连通图为任意删去一条边, 使得原图不连通的无向图.

按照以往的思路, 先统计有根的情况. 设 $b_n$ 为有 $n$ 个节点的有根边双连通图个数, $f_n$ 为有 $n$ 个节点的有根连通图个数. 设根所在的边双连通分量大小为 $k$, 那么该边双连通分量中每个点…

例题

• Luogu P5828 边双连通图计数

点双连通图

点双连通图为任意删去一个点, 使得原图不连通的无向图.

咕咕咕.

例题

• Luogu P5827 点双连通图计数

有标号有向图计数

有向无环图

考虑容斥.

设 $d_n$ 表示有 $n$ 个节点的 DAG 个数, 且不要求弱连通. 记 $A_{n, i}$ 表示有 $n$ 个节点, 其中有 $i$ 个节点入度为 $0$. 有

$$d_n = \mid \bigcap_{i = 0} ^ n A_{n, i} \mid$$

根据容斥原理展开, 得

$$d_n = \sum_{k = 1} ^ n (-1) ^ {k - 1} \sum_{1 \le i_1, \cdots, i_k \le n} ^ {} \mid \bigcup_{j = 1} ^ k A_{n, i_j} \mid$$

注意到后者的并集大小和 $i_j$ 具体取值无关, 也就是在 $n$ 个点中取出 $k$ 个点, 而将这 $k$ 个点删去后剩余 $n - k$ 个点仍然组成 DAG, 且这 $k$ 个点同其余点连边不破坏两边的性质. 因此可得出

$$d_n = \sum_{k = 1} ^ n (-1) ^ {k - 1} \binom{n}{k} d_{n - k} 2 ^ {k (n - k)}$$

我们有 $k (n - k) = \binom{n}{2} - \binom{k}{2} - \binom{n - k}{2}$, 所以原式可化作

$$d_n = \sum_{k = 1} ^ n (-1) ^ {k - 1} \frac{n!}{k! (n - k)!} d_{n - k} 2 ^ \binom{n}{2} 2 ^ {-\binom{k}{2}} 2 ^ {-\binom{n - k}{2}}$$ $$\frac{d_n}{n!\ 2 ^ {\binom{n}{2}}} = \sum_{k = 1} ^ n \frac{d_{n - k}}{(n - k)!\ 2 ^ {\binom{n - k}{2}}} \cdot \frac{(-1) ^ {k - 1}}{k!\ 2 ^ \binom{k}{2}}$$

设 $d_n$ 的组合生成函数为 $D(x)$, 同时设

$$F(x) = \sum\limits_{k = 1} ^ \infty \frac{(-1) ^ {k - 1}}{k!\ 2 ^ \binom{k}{2}}$$

那么有

$$D(x) = D(x) F(x) + 1 \\\ D(x) = \frac{1}{1 - F(x)}$$

一次求乘法逆即可. 时间复杂度 $O(n\log n)$.

简洁的形式背后一定有我不能理解的高妙组合意义…

例题

• Luogu P6295 有标号 DAG 计数

强连通图

强连通图即为任意两点连通的有向图.

设 $n$ 个点有标号强连通图个数为 $d_n$. 考虑强连通图和 DAG 的关系: 强连通图缩点后为一个 DAG. 但是缩点后 DAG 上每个节点所包含的缩点前的点数并不一定为 $1$, 从而无法利用原来的方法计算.

此处有一个思路为, 对 DAG 的式子中容斥系数改写, 也就是将系数和方案数 “放在一起” 计算.

记一个集合 $|S|$ 的权值为 $(-1) ^ {|S|}$, 设 $e_n$ 为任一元素都为强连通图, 且所有强连通图点数和为 $n$ 的集合的权值和. 那么有

$$e_n = - \sum_{k = 1} ^ n \binom{n}{k} e_{n - k} 2 ^ {k (k-1)} \cdot 2 ^ {k (n-k)}$$

其组合意义和 DAG 计数类似, 不再赘述.

此时可以根据 $e_n$ 计算 $d_n$. 考虑到在一强连通图中删去节点 $1$ 及节点 $1$ 所在连通块, 仍可得到一个由强连通图组成的集合. 同时, 在所有强连通图集合中减去不包含节点 $1$ 的情况即为最终答案. 即

$$d_n = -e_n - \sum_{k = 1} ^ {n - 1} \binom{n - 1}{k - 1}\ d_k \cdot e_{n - k}$$

具体实现时可能需要一些技巧, 例如计算 $d_n$ 时可将 $k$ 枚举的上限改为 $n$ 同时做一些处理, 并不会影响答案且便于计算等.

利用多项式求逆, 则时间复杂度为 $O(n \log n)$.

例题

• ZYZOJ #1164 有标号强连通图计数
• COGS 2397 [HZOI 2015]有标号的强连通图计数 II

有标号 / 无标号?

首先定义形式幂级数的 Euler 变换. 即

$$\mathcal E\big(F(x)\big) = \prod_{k = 0} ^ \infty (1 + x ^ k + x ^ {2k} + \cdots) ^ {f_k} = \prod_{k = 0} ^ \infty (\frac{1}{1 - x ^ k}) ^ {f_k}$$

类比于 exp, Euler 变换的组合意义即为选取若干无标号元素组成集合的方案数. 注意无标号元素的影响, 某些在有标号情况下不同的方案在无标号情况下相同.

利用一些运算的技巧, 可以得到

$$\mathcal E\big(F(x)\big) = \exp \left( \sum_{i = 0} ^ \infty f_i \sum_{j = 0} ^ \infty \frac{1}{j} x ^ {ij} \right) = \exp \left( \sum_{k = 0} ^ \infty \frac{1}{k} F(x ^ k) \right)$$

这个结果也可以通过 Polya 定理得到.

无标号图计数

有根树

借助 Euler 变换, 有根树可看作根节点接上若干子树. 设无标号有根树 OGF 为 $F(x)$, 那么有

$$F(x) = x \cdot \mathcal E \big(F(x)\big) = x \cdot \prod_{k = 0} ^ \infty (\frac{1}{1 - x ^ k}) ^ {f_k}$$

两边同时取 $\ln$, 得

$$\ln F(x) = \ln x - \sum_{k = 0} ^ \infty f_k \ln (1 - x ^ k)$$

求导, 得

$$\frac{F(x)'}{F(x)} = \frac{1}{x} + \sum_{k = 1} ^ \infty f_k \cdot \frac{k x ^ {k - 1}}{1 - x ^ k}$$

两侧同时乘 $F(x) \cdot x$, 得

$$x \cdot F(x)' = F(x) + F(x) \left( \sum_{k = 1} ^ \infty k f_k \cdot \frac{x ^ k}{1 - x ^ k}\right)$$

取第 $n$ 项系数, 同时设 $g_n = \sum_{k \mid n} k f_k$. 则有

$$n \cdot f_n = f_n + \sum_{k = 1} ^ n f_k g_{n - k}$$ $$f_n = \frac{1}{n - 1} \sum_{k = 1} ^ n f_k g_{n - k}$$

分治 FFT 计算即可, 时间复杂度为 $O(n \log ^ 2 n)$.

实现时, 在计算 $f_n$ 后枚举 $n$ 的倍数更新 $g$. 注意到如果分治的左端点为 $1$, $g$ 位数不够. 在计算左区间对右区间的贡献时, 需要额外注意.

void solve(int L, int R) { // [L, R)
  if (R-L < 2) {
    f[L] = (L == 1)? 1: 1LL * f[L] * inv[L - 1] % P;
    for (int v = 1LL * L * f[L] % P, i = L; i <= n; i += L)
      g[i] = (g[i] + v) % P;
    return;
  }
  int Mid = (L + R) / 2;
  solve(L, Mid);
  if (L == 1) {
    Mul(f, Mid, g + L, Mid - L, h);
    for (int i = Mid; i < R; ++i) f[i] = (f[i] + h[i - L]) % P;
  } else {
    Mul(f + L, Mid - L, g, R - L, h);
    for (int i = Mid; i < R; ++i) f[i] = (f[i] + h[i - L]) % P;
    Mul(f, R - L, g + L, Mid - L, h);
    for (int i = Mid; i < R; ++i) f[i] = (f[i] + h[i - L]) % P;
  }
  solve(Mid, R);
}

另外存在时间复杂度为 $O(n \log n)$ 的牛顿迭代实现. 在常数和推导过程上都没有什么优势…

无根树

一个经典的套路是只讨论根为重心的情况, 那么用有根树个数 $f_n$ 减去根不是重心的个数即为无根树个数. 此时根据 $n$ 的奇偶性不同存在 $1$ 或 $2$ 个重心, 讨论的情况相对较少.

对于 $n$ 为奇数的情况, 重心唯一. 考虑根节点和任意一条和儿子相连的边, 如果根节点不是重心, 那么该儿子的子树大小 $> \lfloor \frac{n}{2} \rfloor$. 可以得出无根树个数为

$$f_n - \sum_{k = \lfloor \frac{n}{2} \rfloor + 1} ^ {n - 1} f_k \cdot f_{n - k}$$

对于 $n$ 为偶数的情况, 重心不唯一. 如果按照奇数的方法计算, 则另外要注意到根和该儿子都为重心的情况. 此时如果断开这条边, 得到的两棵树不同, 则会在之前的过程中重复统计. 也就是说, 需要在奇数的基础上额外减去

$$\binom{f_{n / 2}}{2}$$

利用有根树的计算方法即可.

例题

• Luogu P5900 无标号无根树计数

后记

似乎这些问题本质上都能归类于 https://oeis.org/transforms2.html?

另外还有其他更为复杂的图计数问题, 以及 “二元生成函数” 之类的科技… 等我学明白了再说吧 (

习题

部分整理自 JOHNKRAM 的课件, 也有一些自己的发现.

1. CF438E The Child and Binary Tree
2. BZOJ 3684 大朋友和多叉树
3. Luogu P4233 射命丸文的笔记
4. HDU 5279 YJC plays Minecraft
5. Luogu P5448 [THUPC2018] 好图计数
6. LOJ #6570 毛毛虫计数
7. LOJ #6684 有根无标号「奇树」计数
8. LOJ #6538 烷基计数 加强版 加强版

参考资料

• 汪乐平, <生成函数, 多项式算法与图的计数>. 2019.1.28.
• 金策, <生成函数的运算与组合计数问题>. 国家集训队 2015 论文集.
• AntiLeaf, COGS 有标号的二分图计数系列.
• Weng_Weijie, 题解 P5900【无标号无根树计数】

---