定义:
有n个标志节点的树的数目等于nn?2(仅是cayley在组合数学中的应用)
1.首先我们假设n为4,即有3个节点
2.这样的话我们就有k个子树,此时k=3
(图1)3.选中其中一个节点C(1n),然后x 再选中不含该节点的一个子树C(1k?1),让这颗子树的根连接到该节点上,这样的话子树就减少了一棵
(图2)(图3)等。。。4.重复操作直到k=1,k从n变成1总共执行了n-1次,所以根据乘法原理,构造出的有确定根节点的树有ans=nn?1?(n?1)!
5.但是对于一棵树来说,它又n-1条边,每条边被选中先后的顺序有(n?1)!种,但是对于树来说,边的先后关系是无关紧要的,所以ans=ans(n?1)!=nn?1
(图4)(图5)6.对于每个树来说,构造树时有确定根节点,每一个树可以将该树中的n个节点均做为根节点,于是乎ans=ansn=nn?2
(图6)(图7)(图8)
学习总结--数学.cayley定理,布布扣,bubuko.com
原文:http://blog.csdn.net/keshuai19940722/article/details/33417525