Prufer 序列 (学习笔记)
概述
可以把树转换到对应的序列，每个唯一的树对应的prufer序列是唯一的
性质
- 对于有n个节点的树，其对应的序列的长度是n-2
- 树中的某个节点的度数是 \(d_i\)，那么它在序列中出现的次数是 \(d_i-1\)次
对于有限多重集的排列公式
假设在一个长度为T的序列，其中元素i会出现\(t_i\)次，共有m种元素，我们可以推出他的排列公式：
-
首先不考虑重复，让T个元素全排列
-
对于同一类的元素，如果交换位置，那么序列是一样的，所以我们就需要除一些数去去重
如对于第 1 种，就会\(t_1!\)种重复的排列，需要去除以\(t_1!\)去重 -
以此类比，我们就可以得出最后的公式
\[\frac{T!}{\prod_{i=1}^{m} t_i!} \]
最后公式
对于一个树的Prufer序列全排列的公式为：
\[\frac{(n-2)!}{\prod_{i=1}^{m} (d_i-1)!}
\]