Prufer codes与Generalized Cayley's Formula

时间:2022-10-14 18:39:26

Prufer序列

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

    1.若当前树中只剩下两个点,退出,否则执行2。

    2.找到树中编号最小的节点,将与它相连的那个点的编号加入Prufer序列的末尾,并将这个叶子删除。返回1。

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

    1.令A={1,2,...,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,...,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,m,a,b,求有多少个n个点的带标号无根树,满足所有边权在[1,m]中,且a到b的简单路径长度为m。

  显然枚举a,b中的边数,那么a,b中间的点有$P_{n-2}^{i-1}$种方案,这中间i条边的边权共有$C_{m-1}^{i-1}$种方案,其余边权有$m^{n-i-1}$种方案,而剩下的就是n个点组成i+1棵树,其中在a,b简单路径上的i+1个点分别属于其中一棵树的方案数,也就是$f(n,i+1)=(i+1)n^{n-i-2}$。

定理拓展:

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

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

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

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