【问题1】有根树的计数

　　用n个相同顶点能够构成多少种结构不同的有根树呢？在n=4的时候，有下面4种构造方法：

　　　　　　　　　　　　

　　我们不妨假设用n个顶点能够构成种有根树。那么，很显然有=1。当n>1时，这棵树的结构必然是：
　　　　　　　　 　　　　　
　　即这棵有根树包含t棵子树，第i棵子树包含的顶点个数是 。那么，必然有 。

　　为了便于记数，我们不妨假设含有1个顶点的子树有个，含有2个顶点的子树有个，……，含有n-1 个顶点的子树有个。那么，有 。

　　含有k的顶点的子树有个，而这个子树每个均有种构造方法。我们假设这个子树中有个采用的是第1种构造方法，有个采用的是第2中构造方法，……，有个采用的是第种构造方法，那么，有。这个方程非负整数解的个数就是这个包含k个顶点的子树的构造方案总数①。

　　因此，用n个顶点可以构造的有根树总数为：

　　………… 等式1

　　当然，这里有n>1。

　　
　


　　注：①关于方程的非负整数解个数问题，参见有关组合数学书籍。

　　相关键接：树的计数(一)
　　　　　　　树的计数(二)
　　　　　　　树的计数(三)　　　　　
　　　　　　　树的计数(四)