xzm2019

【转】Prufer codes与Generalized Cayley's Formula
最近补cf的1113F/1109D的时候要用到这个东西,但是找了半天也没找到什么,只看到一个别人也是这场比赛赛后写...
扫描右侧二维码阅读全文
18
2019/02

【转】Prufer codes与Generalized Cayley's Formula

最近补cf的1113F/1109D的时候要用到这个东西,但是找了半天也没找到什么,只看到一个别人也是这场比赛赛后写的这个学习笔记,给搬运一下。

原文链接:https://www.cnblogs.com/HocRiser/p/10390772.html
原文作者:HocRiser
原文发布时间:2019-02-17 12:55

Prufer序列

在一棵$n$个节点带标号树中,我们认为度数为1的点为叶子。$n$个点的树的Prufer序列是经过下面流程得到的一个长度为$n-2$的序列。

  1. 若当前树中只剩下两个点,退出,否则执行2。
  2. 找到树中编号最小的节点,将与它相连的那个点的编号加入Prufer序列的末尾,并将这个叶子删除。返回1。

显然,每棵树都唯一对应一个Prufer序列,而每个Prufer序列也唯一对应一棵树。可以通过一下流程得到这棵树。

  1. 令$A=\{1,2,\cdots,n\}$,不断重复2直到Prufer序列为空。
  2. 找到$A$中最小的不在Prufer序列中的点,将其与Prufer序列首元素连边,然后同时删除这个点与序列首元素。
  3. 此时$A$中还剩下两个点,将这两个点连边。

根据以上流程,不难发现:若点$i$在树中的度数为$a_i$,则它在Prufer序列中会出现$a_i-1$次。


Cayley's Formula

Prufer序列中的每个元素都可以从1取到n,且每种方案会唯一对应一棵带标号无根树。

所以,由于Prufer序列共有$n^{n-2}$个,n个点的带标号无根树就有$n^{n-2}$种。

拓展:

  1. 显然,$n$个点的带标号有根树有$n^{n-2}$种。
  2. 当树中每个点的度数$a_i$都已经确定后,由Prufer序列得,满足条件的树共有$\frac{(n-2)!}{\prod a_i!}$种。

例题:BZOJ1005,BZOJ1211,BZOJ1430


Generalized Cayley's Formula

已知$n,k$,求$f(n,m)$表示$n$个点组成的共有$m$棵树的森林,且$1,2,\cdots,m$分别属于不同的树,的方案数。

先给出结论:$f(n,m)=m\cdot n^{n-m-1}$。

显然可以发现$f(n,1)=n^{n-2}$

证明:

显然,$f(1,1)=0$,$f(n,0)=0(n \geq 1)$。
数学归纳,假设对于所有$i<n$的$f(i,j)$都已证明。
考虑1号点属于的那棵树,枚举1号点的度数$i$,则删除后这张图会变成$n-1$个点,$m+i-1$棵树。
$f(n,m)=\sum\limits_{i=0}^{n-m}\binom{n-m}{i}f(n-1,m+i-1)$
将原式代入,有$f(n,m)=\sum\limits_{i=0}^{n-m}\binom{n-m}{i}(m+i-1)(n-1)^{n-m-i-1}=mn^{n-m-1}$
命题得证。

拓展:显然$n$个点组成有根树森林的方案为$\sum\limits_{k=1}^{n}n^{n-k-1}\times k\times \binom{n}{k}$

应用:CF1109D


定理拓展

$n$个带权的点,定义每条边的权值为相连的两个点的权值之积,定义一棵树的权值是所有边的权值之积,求所有树的权值和。

相当于每棵树中每个点的权值的度数次方的和。考虑Prufer序列,每个点都恰出现度数-1次。于是根据乘法分配律,答案为(所有点权值之积)*(所有点权值之和)$^{n-2}$。

这个推论包含了上面所有定理。当所有点权值取1时,就是Cayley's Formula。当将点1~m缩成一个权值为m的点时,就是Generalized Cayley's Formula。

以上所有似乎都可以用Matrix Tree那一套理论通过化简行列式得到。

Last modification:February 28th, 2019 at 09:25 am
If you think my article is useful to you, please feel free to appreciate

One comment

  1. 吴逸恒

    Prufer序列的构造中第二步中,如果最小编号节点不是叶子节点会发生什么

Leave a Comment