如何阳间的数有向图（详细揭秘）

咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕 --- 没想到吧我没咕，上面只是一个防止预览的 padding  打个预防针：可以 K，反正我也拦不了您，但是 CH4 要点赞，不然评论有概率被删除 然后内容挺平凡的，，，如果看完觉得毫无信息量不要喷我 --- 定义序列 $f_n$ 的 EGF 和 GGF 为： $$ {\rm A}(x)=\sum_nf_n\frac{x^n}{n!},\qquad{\bf A}(x)=\sum_n\frac{f_n}{2^\binom n2}\frac{x^n}{n!} $$ 那么设 ${\bf C}(x)={\bf A}(x){\bf B}(x)$，有： $$ [x^n]{\bf C}(x)=2^\binom n2n![x^n]\left(\sum_i\frac{a_i}{2^\binom i2}\frac{x^i}{i!}\right)\left(\sum_j\frac{b_j}{2^\binom j2}\frac{x^j}{j!}\right)=\sum_{i+j=n}\binom ni2^{ij}a_ib_j $$ 相当于从 $\mathcal A$ 中选 $i$ 个点，$\mathcal B$ 中选 $j$ 个点，给它们分配标号，然后中间随意连边。为了方便，我们规定这些边都是从 A 连向 B 的。如下图所示：  然后定义两个 EGF ${\rm A}(x),{\rm B}(x)$ 的点积 ${\rm A}(x)\odot{\rm B}(x)$ 为： $$ {\rm A}(x)\odot{\rm B}(x)=\sum_na_nb_n\frac{x_n}{n!} $$ 设 ${\rm G}(x)$ 为任意**无向图**的 EGF，${\bf D}(x)$ 为任意**有向图**的 GGF，${\bf Set}(x)$ 为没有边的图的 GGF，那么有： $$ {\rm G}(x)={\bf D}(x)=\sum_n2^\binom n2\frac{x^n}{n!},\qquad{\bf Set}(x)=\sum_n\frac1{2^\binom n2}\frac{x^n}{n!} $$ 然后对于任意序列 $a_n$ 的 EGF 和 GGF ${\rm A}(x),{\bf A}(x)$，有如下的关系： $$ {\rm A}(x)={\rm G}(x)\odot{\bf A}(x),\qquad{\bf A}(x)={\bf Set}(x)\odot{\rm A}(x) $$ 证明也非常显然： $$ \begin{aligned} {\rm G}(x)\odot{\bf A}(x)&=\left(\sum_n2^\binom n2\frac{x^n}{n!}\right)\odot\left(\sum_n\frac{a_n}{2^\binom n2}\frac{x^n}{n!}\right)=\sum_na_n\frac{x^n}{n!}={\rm A}(x)\\ {\bf Set}(x)\odot{\rm A}(x)&=\left(\sum_n\frac1{2^\binom n2}\frac{x^n}{n!}\right)\odot\left(\sum_na_n\frac{x^n}{n!}\right)=\sum_n\frac{a_n}{2^\binom n2}\frac{x^n}{n!}={\bf A}(x)\\ \end{aligned} $$ 设 ${\bf DAG}(x,z)$ 为固定点数和零入度点数的 DAG 个数的 GGF，${\bf DAG}(x)$ 为仅固定点数的 GGF。 考虑从一张 $d$ 个点的，没有边的图向 DAG 任意连边。那么最终得到的 DAG 中至少有 $d$ 个零入度点。于是我们可以得到下面的式子： $$ {\bf Set}(xz){\bf DAG}(x)={\bf DAG}(x,z+1) $$ ${\bf Set}(xz)$ 中 $xz$ 的意义是，每个点一定是一个零入度点。${\bf DAG}(x,z+1)$ 中 $z+1$ 的意义为，让 $z$ 的指数标记**至少**有几个零入度点。换句话说，每个零入度点可以被标记也可以不被标记。  *图：将无边图向 DAG 任意连边。* 将上式代入 $z=-1$，可得 ${\bf Set}(-x){\bf DAG}(x)={\bf DAG}(x,0)$。由于只有空图没有零入度点，所以 ${\bf DAG}(x,0)=1$，即 ${\bf DAG}(x)=1/{\bf Set}(-x)$。 DAG 数完了，然后来数强连通图。设 ${\rm SCC}(x),{\bf SCC}(x)$ 为固定点数的强连通图数量的 EGF 和 GGF。**注意：这里认为空图不是强连通图。** 考虑任意图缩点之后会变成 DAG，DAG 中每个点都会是一个强连通分量。我们称 DAG 中的零入度点对应的强连通分量为**类源 SCC**。然后设 ${\bf D}(x,z)$ 为固定点数和类源 SCC 数的有向图个数的 GGF。 考虑和上面类似的方法。我们将「$d$ 个强连通图」向「任意有向图」任意连边。那么最终得到的有向图中至少有 $d$ 个类源 SCC。于是我们可以得到下面的式子： $$ \left({\bf Set}(x)\odot e^{z{\rm SCC}(x)}\right){\bf D}(x)={\bf D}(x,z+1) $$  *图：将 SCC 向任意图任意连边。* 其中 $e^{z{\rm SCC}(x)}$ 代表任意多个强连通图（类源 SCC）$z$ 用来标记其个数。${\bf Set}(x)$ 用来将 EGF 转为 GGF，根据公式 ${\bf Set}(x)\odot{\rm A}(x)={\bf A}(x)$。 然后代入 $z=-1$，可得 $$ \begin{aligned} \left({\bf Set}(x)\odot e^{-{\rm SCC}(x)}\right){\bf D}(x)&={\bf D}(x,0)\\ \left({\bf Set}(x)\odot e^{-{\rm SCC}(x)}\right){\bf D}(x)&=1\\ {\bf Set}(x)\odot e^{-{\rm SCC}(x)}&=\frac1{{\bf D}(x)}\\ {\rm G}(x)\odot{\bf Set}(x)\odot e^{-{\rm SCC}(x)}&={\rm G}(x)\odot\frac1{{\bf D}(x)}\\ e^{-{\rm SCC}(x)}&={\rm G}(x)\odot\frac1{{\bf D}(x)}\\ e^{-{\rm SCC}(x)}&={\rm G}(x)\odot\frac1{{\rm G}(x)}\\ {\rm SCC}(x)&=-\ln\left({\rm G}(x)\odot\frac1{{\rm G}(x)}\right)\\ \end{aligned} $$ 于是我们得到了强连通图个数的计算方式。