图计数

图计数

$n$ 个点的有标号 DAG

$h_n$ 表示 $n$ 个点的DAG方案数

$f_{n,i}$ 表示一共 $n$ 个点,其中至少 $i$ 个是汇点的方案数

$g_{n,i}$ 表示一共 $n$ 个点,其中恰好 $i$ 个是汇点的方案数

于是有如下恒等式:

然后得到

然后令 $H(x)=\sum_{i=0}^\infin \frac{h_i}{2^\binom i2 i!}x^i$ , $G(x)=\sum_{i=1}^\infin \frac{(-1)^{i-1}}{2^\binom i2 i!}x^i$ 有 $H(x)=1+H(x)G(x)$

所以 $H(x)=\frac{1}{1-G(x)}$ ,使用多项式求逆即可

对 $h_n=\sum_{i=1}^n(-1)^{i-1}2^{i(n-i)}\binom ni h_{n-i}$ 还有一个组合上的解释:

考虑 $\sum_{i=0}^n(-1)^i2^{i(n-i)}\binom ni h_{n-i}$ 这个式子,这里每个 $g_i$ 被其大小为奇数的子集贡献 $-1$ ,大小为偶数的子集贡献 $+1$ ,所以得到 $\sum_{i=0}^n(-1)^i2^{i(n-i)}\binom ni h_{n-i}=g_0$ 去掉 $i=0$ 时的贡献得到 $\sum_{i=1}^n(-1)^i2^{i(n-i)}\binom ni h_{n-i}=-g_1-g_2-g_3-\cdots -g_n$ 所以 $h_n=g_1+g_2+g_3+\cdots=\sum_{i=1}^n(-1)^{i-1}2^{i(n-i)}\binom ni h_{n-i}$

注意:$\binom i2$ 不要写成 $i\times (i-1)$ 忘除以 $2$ 了。。。以及这个好像 oeis 上叫什么 3-multigraph 又可以出毒瘤题了


$n$ 个点有标号的弱连通 DAG

解一:

感性理解一下,用上面的东西直接求个ln即可 (怎么学X写题解)

解二:

令 $f_n$ 表示上面求出来的 $n$ 个点不要求联通DAG

$g_n$ 表示要求联通的DAG

用可以联通可以不连通的数量减去一定不连通的就是答案,枚举 $1$ 所在连通块大小有

(实际上和求ln等价的)

如果要拆开的话就是

令 $F(x)=\sum_{i=0}^\infin \frac{f_i}{i!}x^i$ , $G(x)=\sum_{i=1}^\infin \frac{g_i}{i!}$

由上面得到

所以这玩意确实是直接求 $\operatorname{ln}$ 即可


给定一无向图的边集,计算给所有无向边定向使得 $1$ 号点恰好能访问到点集 $S$ 的方案数

设 $f_S$ 为只考虑 $S$ 内部的无向边定向后的答案, $ans_S$ 为题目中所求的答案,则 $ \complement_U S$ 与 $S$ 之间的边一定是从前者到后者,记 $E_S$ 表示 $S$ 内部连边的数量,则


$n$ 个点的仙人掌

$C(x)=x\exp((\sum_{i\geq 2}\frac{C(x)^i}{2})+C(x))=x\exp(\frac{2C(x)-C(x)^2)}{2-2C(x)}{})$

令 $G(C(x))=x\exp(\frac{2C(x)-C(x)^2}{2-2C(x)})-C(x)$

$C(x)=C_0(x)-\frac{G(C_0(x)))}{G’(C_0(x))}$


$n$ 个点的有标号点双

记 $n$ 个点的有根连通图的 EGF 为 $H(x)$,$n$ 个点的点双个数的 EGF 为 $B(x)$

对于一个有根连通图,找到根节点所在的点双,删掉点双内部所有的连边,一定会形成一个中间的根和若干个有根的连通块。所以得到 $H(x)=x\times \sum_{i=0}^\infin b_{i+1}\frac{(H(x))^i}{i!}=xe^{B_1(H(x))}$ 其中 $B_1(x)=\sum_{i=0}^\infin b_{i+1}\frac{x^i}{i!}=B`(x)$

有 $H^{-1}(H(x))=x,\frac{H(x)}{e^{B_1(H(x))}}=x$ 比较系数得到 $H^{-1}(x)=\frac{x}{e^{B_1(x)}}$

得到 $B_1(x)=\ln(\frac{x}{H^{-1}(x)})$

求 $B_1(x)$ 第 $n$ 项:

考虑拓展拉格朗日反演的形式

令 $ff(H^{-1}(x))=B_1(x)=\ln(\frac{x}{H^{-1}(x)})$ ,得到 $ff(H^{-1}(H(x)))=ff(x)=\ln(\frac{H(x)}{x})$ 。

所以 $[x^n]B_1(x)=[x^n]ff(H^{-1}(x))=\frac 1n[x^{n-1}]ff’(x)(\frac{x}{H(x)})^n$


$n$ 个点的有标号边双

设 $n$ 个点的有根连通图的 EGF 为 $H(x)$,$n$ 个点的边双个数的 EGF 为 $B(x)$

考虑一个有根联通图,令根节点所在的边双的点数为 $n$,选根是这个边双中的哪一个有 $n$ 种选法。考虑缩边双形成的 BCC 树,根节点所在的超级点会有若干子树,每个子树都是一个有根联通图,可以选超级点中任意一个连边,一个子树 EGF 就是 $nH(x)$ ,若干个就是 $e^{nH(x)}$

得到 $H(x)=\sum_{i}i\times \frac{b_i}{i!}x^ie^{iH(x)}=\sum_{i=0}^\infin\frac{b_{i+1}}{i!}x^{i+1}e^{(i+1)H(x)}=xe^{H(x)}\sum_{i=0}^\infin\frac{b_{i+1}}{i!}(xe^{H(x)})^i=B_1(xe^{H(x)})$, 其中 $B_1(x)=x\times\sum_i\frac{b_{i+1}}{i!}x^i=xB’(x)$ 于是得

到 $H(x)=B_1(xe^{H(x)})$

求 $B_1(x)$ 第 $n$ 项:

$x=H(H^{-1}(x))=B_1(H^{-1}(x)e^x)$

$G(x)=xe^{H(x)}$ 所以 $B(G(x))=H(x)$,$B(x)=H(G^{-1}(x))$

$[x^n]B_1(x)=H(G^{-1}(x))=\frac 1n[x^{n-1}]H’(x)(\frac{x}{G(x)})^n$


$n$ 个点有标号强连通图

令 $h_n$ 表示 $n$ 个点有向图个数。定义集合 $S$ 的权值是 $(-1)^{|S|}$,设 $e_n$ 表示(这个集合里所有元素都是强连通图)所有这样的 集合内元素总点数为 $n$ 的集合的权值和。


给定无向图的边的子集满足形成边双的方案数

记 $f(S)$ 为 $S$ 形成连通图方案数,$h(S,T)$ 为 $S$ 分成若干块且每块都和 $T$ 连恰好一条边的方案数

$edge(S,T)$ 直接 $E(S\oplus T)-E(S)-E(T)$即可


给定有向图的边的子集满足形成强连通的方案数

$f[S]$ 表示把集合 $S$ 分为非强连通分量的方案数

$h_k[S]$ 表示把集合 $S$ 分为 $k$ 个 $SCC$ 的方案数

$ans[S]$ 表示把集合 $S$ 分为 $1$ 个 $SCC$ 的方案数(也即是 $h_1[S]$ )

对于 $edge(T,S\backslash T)$ , 令 $u=\min S\backslash T$

后两项可以通过预处理一个点的出度集合和入度集合来快速计算

Q: 算 $f[S]$ 时要用到 $g[S]$ 但算 $g[S] $ 时不是应该加上当前的 $ans[S]$ 吗,$ans[S]$ 又要通过 $f[S]$ 求?

A: 想一下我们现在求的是什么:当前情况的合法状态数 $ans[S]$ 。这个要通过 $2^{E[S]}-f[S]$ 实现,那么就要把之前算的答案导致的不合法情况容斥掉,而 $g$ 的意义只是为了我们后面再算的时候降低复杂度,是我们“定义”出来的一个值,没有什么实际含义,即我们只需要算之前的 $g[T]$ 导致的不合法情况并删除,剩下的就是现在合法的情况数,然后再用这个去更新现在的 $g[S]$ 以便以后用到的时候值正确