关于树的计数

目录

1. $prufer$ 序列
2. $Cayley$ 公式

$prufer$ 序列

是指对于一个带标点的无根树,找出编号最小的叶子节点,写下与它相邻的节点编号,然后删除这个叶子节点。操作直到只剩两个节点。

可以证明每一个序列只对应一棵树,每一棵树也只有唯一一种序列。

$Cayley$ 公式

一个带标号的完全图,存在 $n^{n-2}$ 棵带标号的无根树。可以用 $prufer$ 序列证明。

推广:

1.对于有 $n$ 个点 $k$ 个联通块的森林,并且一直 $1,2,...k$ 各属于不同联通块的森林的方案数为
$$
f(n,k)=i imes n^{n-i-1}
$$

原文地址:https://www.cnblogs.com/Jessie-/p/10504817.html