奇怪的计数增加了
这里有一些常见的图计数套路
由于本人多项式功底为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\i | 1 | 2 | 3 | |
|---|---|---|---|---|
| 1 | 1 | |||
| 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$个位置, 每个位置填括号使整个序列成为一个合法括号序. 问期望一对括号的距离是多少?