树的计数

Cayley 定理

• Cayley 定理：$n$ 个有标号的点构成无根树的方案数为 $n^{n-2}$
• 广义 Cayley 定理：给定 $n$ 个点中的 $k$ 个，要求构造一个 $k$ 棵树的森林，并且给定的点两两不位于同一棵树。方案数为 $k\times n^{n-k-1}$