• 时间:
  • 分类: OI
摘要： 文章介绍了多种图计数问题及其解法，包括无向图计数、Prufer序列与无根树计数、二叉树计数、无向连通图计数、二分图计数、基环树计数以及一个期望题。无向图计数通过计算连边方式得出，Prufer序列用于证明Cayley公式，二叉树计数涉及Catalan数，无向连通图计数采用容斥原理，二分图计数通过染色方案数计算，基环树计数则涉及环排列。期望题涉及合法括号序的期望距离计算。
这里有一些常见的图计数套路
由于本人多项式功底为0, 所以不会优化式子.
如果你发现式子有问题或者是会优化式子, 麻烦直接告诉我.

无向图计数

$n$节点的无向图有多少种?

为了提高根本没人会看的博客的阅读体验, 我们先从简单的开始.

考虑每个点最多向每个剩余点连一条边, 共$n-1$条,
由于是无向图, 每条边会被两个端点各计算一次,
所以一张无向图最多有$\frac{n(n-1)}{2}$条边.

因为每条边独立地有连和不连两种情况,
所以共有$2^{\frac{n(n-1)}{2}}$种连边方式.

Prufer序列

有标号的无根树有多少种?

Cayley公式

Cayley公式指出, $n$节点的无根树有$n^{n-2}$种.

Prufer序列展示了一个数列如何与一棵有标号无根树双射,
也就是说, 符合某个规则的序列数量就是有标号无根树的数量.

Prufer序列是为了证明Cayley公式而设计的.

构造

尝试证明序列与有标号无根树之间的双射, 这可以帮助我们理解这个公式.
当然, 如此简单的公式我们也可以直接记忆.

如果给出一棵树, 如何构造它的Prufer序列?

根据Prufer序列的定义, 每次删去编号最小的叶节点并记录它所连的边, 直到剩余两个节点.

如果给出一个数列, 如何用Prufer方式构造一棵树?

观察构建方式, 我们得到一些信息:

  • 剩下的两个点中必有$n$号点.
  • 点$i$的度数是它在序列中出现次数$+1$.
  • 根据上一条, 没出现在序列中的都是叶子节点.

当我们得到所有叶子节点之后, 就可以按照删点方式加点了.
序列第一个值就是最小叶节点的连边, 以此类推.
维护一个小顶堆, 如果有产生新的叶节点就将它加入堆.
最后剩下两个点, 直接连接.

可以发现, 一棵树可以构造出一个唯一的序列, 一个序列也可以构造出一棵唯一的树.

二叉树计数

N点的无标号二叉树有多少种?(二叉树默认有根,对称不算同一种)

递推方式

对于一个$N$节点的二叉树, 我们可以枚举一棵子树的大小, 此时另一棵子树的大小也确定了.
设$f_i$表示$i$节点的子树构造方案.

$$ f_i=\sum_{j=0}^{i-1}{f_j \times f_{i-1-j}} $$

Catalan数

我们发现上面那个式子就是Catalan数的递推式, 所以也可以直接用Catalan数公式求解.

我们可以考虑合法括号序与二叉树之间的双射.
考虑Catalan数递推式的由来, 每次添加一个括号时, 枚举括号内和括号右的合法括号序数量.
拓展到二叉树, 每次对第一个左括号做匹配, 括号内的就是左子树, 括号右就是右子树.

<!--

DAG计数

有标号DAG有多少种?

这里给出一种简单粗暴的计数方式.

考虑先计算无标号图每次增加一个点, 贡献是向原先点集连边的方案数.
然后我们发现如果第2,3个点都只向第1个点连边, 这样就会算重.

然后我们将重点放在处理最外层度数为$1$的点上.

设$f_{i,j}$为$i$点图, 有$j$个外层点.
-->

无向连通图计数

有标号无向连通图有多少种?

考虑一个容斥, 用所有连边方式减去不连通的连边方式.

我们钦定一个点, 枚举它所在的联通块大小.
设联通块的大小为$j$, 组合一下选入的$j$个点然后乘上$j$个点连通图的方案数$f_j$,
联通块外随便连就是$2^{\frac{(n-j)(n-j-1)}{2}}$.

$$ f_i= 2^{\frac{n(n-1)}{2}} -\sum_{j=1}^{i-1}{ C_{i-1}^{j-1} \times f_j \times 2^{\frac{(i-j)(i-j-1)}{2}} } $$

这样我们就可以$O(n^2)$递推处理了.

二分图计数

$n$点有标号$m$联通块的二分图有多少种?

转换一下思路, 尝试求出染色后的二分图个数$S$(不一定联通).
枚举一侧的点集, 然后两边任意连边.

$$ S_n= \sum_{i=0}^{n}{ C_{n}^{i} \times 2^{i(n-i)} } $$

同时我们设$f_{i,j}$为$i$个点$j$个联通块的二分图数量,
用类似无向连通图计数的方式, 钦定一个点枚举联通块大小可以得到:

$$ f_{i,j}= \sum_{k=1}^{i-j+1}{ C_{i-k}^{k-1} \times f_{k,1} \times f_{i-k,j-1} } $$

看到这里我们发现没办法求出$f_{i,1}$, 别灰心, 我们尝试在$S$和$f$之间建立联系.
对于每个联通块我们有$2$种染色方案, $i$个联通块就是$2^{i}$种染色方案.

$$ S_n=\sum_{i=1}^{n}{ f_{n,i} \times 2^{i} } $$

这里应该有个表格.

j\i123
11
2 1
3 1

我们的$S_n$是对一列的$f$进行带参求和, 所以当我们得到了这一列除$f_{n,1}$外的值, 我们就可以得到$f_{n,1}$.
所有的$f_{i,i}$都是显然的,
而$f_{i,j}$的递推只需要用到$i'<i$且$j'<j$的值, 通过上述方法可以得到.

具体的, 我们第一维按$i$升序枚举, 第二维按$j$降序枚举.
当$j>1$时我们直接递推, 当$j=1$时我们通过$S_n$求差得到.

基环树计数

有标号基环树有多少种?

这道题其实比上面那个简单QwQ.

如果我们得到了一个森林, 只要对所有树环排列即可.
那么设$f_{i,j}$为$i$个点$j$棵树的方案数.

每次选$k$个点作为一棵树加入答案:

$$ f_{i,j}= \sum_{k=1}^{i-j+1}{ C_{i}^{k} \times f_{k,1} \times f_{i-k,j-1} } $$

$f_{k,1}$用Cayley公式求解.

最后答案乘上环排列就好:

$$ \sum_{i=3}^{n}{ f_{n,i} \times \frac{(i-1)!}{2} } $$

一道期望题

为什么会出现在这里呢? 大概是因为上课讲了就顺便放在这里吧.

数轴上$2n$个位置, 每个位置填括号使整个序列成为一个合法括号序. 问期望一对括号的距离是多少?

标签: none

添加新评论