目录

一，二项树（binomial tree）

二，二项树的母函数

三，二项树的节点数

一，二项树（binomial tree）

二项树是一组固定的递归定义的树：

B0是一个单节点的树，

Bn是一棵n叉树，根节点有n个孩子，分别是B0，B1......B n-1

二，二项树的母函数

对于Bn，它的深度为n，我们定义它的母函数：

  , 其中si是第i层的节点数目

根据二项树的定义，我们可以得到母函数的递推式：

根据此递推式，可以求出来，

所以，二项树Tn的母函数是二项式(1+x)^n

三，二项树的节点数

二项树的第i层的节点数是二项式系数C(n, i)

二项树的节点总数是2^n

文章来源: blog.csdn.net，作者：csuzhucong，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nameofcsdn/article/details/115375700