Cayley定理

Cayley 定理：给定(n)个点（互不相同），它们所构成的无根树的个数为(n^{n-2})。
证明：可以考虑prufer数列，每一棵无根树唯一对应一个有(n-2)个元素的prufer数列，并且，每一个prufer数列都唯一对应一棵无根树，所以，共有(n^{n-2})种。
Update on 2021.5.6：我是屑/kk，Cayley 定理是假设该图中有 (m) 个联通块，联通块内的点的个数分别为 (a_1,a_2,dots,a_m) 并且 (a_1+a_2+dots+a_m=n)，那么通过加 (m-1) 条边使得所有联通块联通的方案数是 (n^{m-2} prod_{i=1}^m a_i)，证明依然是考虑 Prufer 序列。
广义 Cayley 定理：（参照jklover的博客)
(n)个标号节点形成一个有(k)颗树的森林,使得给定的(k)个点没有两个点属于同一颗树的方案数为(k cdot n^{n-k-1})。
证明：咕咕咕，我也不会，就当成结论记吧