Cayley公式 及其 简单拓展

emmm…

就小记一下好了, 最近在努力从初赛的种种中走出了…

Question: 对于n节点的无根树, 共有几种不同的形态 ?

Answer: n^{n-2}

引入Prüfer编码来帮助我们更好的解决问题:

对于一棵树, 进行如下操作:

  1. 寻找当前 度=1 的节点(叶), 在序列中添加其邻节点编号并且删除该点
  2. 重复上述操作, 直到图中剩两个点为止

命题

记形成的序列名为Prüfer编码

易知该序列长度为n-2, 假使证明树形态与Prüfer编码一一对应, 答案显然


每种树形态对应一个Prüfer编码

易知…

每个Prüfer编码对应一种树形态

可知:

  1. 原图的叶节点一定不会在Prüfer编码中

考虑要么这个叶节点在过程中被删除, 要么没有删除, 但是最后留下了一条边, 所以均不会在序列出现.

  1. 非叶节点一定出现在Prüfer编码中

由于最后只剩下一条边, 而非叶节点至少会有2条边与之相连, 那么就知道一定有对其的操作

构造方法:

根据前2种性质, 每次选从未在序列中出现, 且最小的数字, 操作该数与当前序列的第一位相连, 并删除序列首元素, 重复n-2​遍, 最后将未操作的两个数直接相连即可!

证毕

tricky性质:

n个节点的度依次为D_1 D_2 \cdots D_n的无根树共有\frac{(n-2)!}{\prod_{i=1}^n(D_i-1)!}个,因为此时Prüfer编码中的数字i恰好出现D_i-1

习题

题面:

一开始森林里面有N只互不相识的小猴子,它们经常打架,但打架的双方都必须不是好朋友。每次打完架后,打架的双方以及它们的好朋友就会互相认识,成为好朋友。经过N-1次打架之后,整个森林的小猴都会成为好朋友。
现在的问题是,总共有多少种不同的打架过程。 比如当N=3时,就有{1-2,1-3}{1-2,2-3}{1-3,1-2}{1-3,2-3}{2-3,1-2}{2-3,1-3}六种不同的打架过程。

sol

ans=n^{n-2}\cdot(n-1)!

发表评论

电子邮件地址不会被公开。 必填项已用*标注