树的计数公式推导 首先提出树相似的定义，如果两棵树T1和T2相似，那么须满足下列条件之一：（1） T1和T2同时为空树（2） T1和T2不为空树，则T1和T2的所有子树分别依次对应相似（显然这里只讨论有序树，树的孩子有序）树的计数问题描述为：给定一棵树的结点总数n，由n个这样的结点能组成多少棵互不相似的树呢？为了解决这个问题，首先把树转换成二叉树，因为一棵树可以唯一的转换成与之对应的二叉树，转换的方法是二叉树中的左孩子表示树中的最左孩子，二叉树中的右孩子则表示树中的相邻右兄弟，按这样的方法可以得到唯一的一棵二叉树，且它的根结点没有右子树（因为树的根结点没有兄弟）。根据一一对应关系，树的计数问题可以转换成等价的二叉树的计数问题，这使讨论更加方便容易。设n个结点可以表示的二叉树计为bn，先从简单的开始：如果n=0，显然b0=1如果n=1，显然b1=1如果n=2，b2=2    N    N   /      \  N        N如果n=3,b3=5如果n再大一些，就很难绘出来了。当n>1时可以得到一个递推公式，此时有一个根结点，剩下n-1个结点可以用来构成两个左右子树，设左子树有i个结点，则右子树就有n-i-1个结点，由左右子树的不对称性（前面提到只讨论有序树），所以有b[i]*b[n-i-1]种构成方法，当i取值不同结果也不同，所以所有的构成方法为各种i值情况的和，所以bn=∑b[i]*b[n-i-1]，i从0取到n-1所以整个数列可以递推的定义为：b[0]=b[1]=1b[n]= ∑b[i]*b[n-i-1]，i从0取到n-1 为了求出bn的通项，需要引入构造函数B[n]，在这之前首先提一下广义的二项式定理。 二项式是这样的形式：(a+b)^p，a+b为一个代数和形式，p为非0的实数。作函数F[x]=(a+x)^p，由幂极数在x0=0处展开F[x]得：F[x]=m0+m1x+m2x^2+…+mnx^n+…其中mi=F^(i)[0+]/i!，F^(i)[0+]定义为F[x]的i阶导数在x=0处的值或者极限，且0!=1，0阶导数为F[x]本身不难得出：F^(i)[x]=p(p-1)…(p-i+1)(a+x)^(p-i)，所以mi=[p(p-1)(p-2)…(p-i+1)/i!]*a^(p-i)x^i引入一种记法：[p,i]=p(p-1)(p-2)…(p-i+1)/i!，如果p为正整数且小于i，则[p,i]正是组合数C(i,p)，当p限定为正整数的情况下得出的即为一般形式的二项式定理。所以，F[x]=(a+x)^p=∑[p,i]a^(p-i)x^i,i从0取到无穷大，作代换x=b，即(a+b)^p=∑[p,i]a^(p-i)b^i,i从0取到无穷大，这就是二项式的一般展开级数。 下面引入B[x]的定义，由前面的bn定义：B[x]=b0+b1x+b2x^2+…+bnx^n+…=∑bnx^n ，n从0取到无穷大作乘积B[x]^2=b0b0+(b0b1+b1b0)x+(b0b2+2b1b1+b2b0)x^2+…=∑_i{∑_j b[j]b[i-j]}x^i ，i从0取到无穷大，j从0取到i[再根据bn的定义知]=∑_ib[i+1]x^i ，i从0取到无穷大[两边同乘x]xB[x]^2=∑_ib[i+1]x^(i+1) ，i从0取到无穷大即xB[x]^2=B[x]-b0 ，b0=1所以得方程：xB[x]^2-B[x]+1=0解得 B[x]=( 1±(1-4x)^(1/2) )/2x考虑到B[0+]=b0=1，所以B[x]=( 1-(1-4x)^(1/2) )/2x中间有一个二项式(1-4x)^(1/2)，展开得(1-4x)^(1/2)=∑[1/2,n](-4x)^n ，n从0取到无穷大和式第1项为1，刚好与前面的1减掉，同时乘进一个-1，所以B[x]=(1/2)∑[1/2,n](-1)^(n-1)2^(2n)x^(n-1) ，n从1取到无穷大（n=0项已减掉）既然n从1取到无穷大，则n-1从0取到无穷大，作代换m=n-1，得B[x]=∑{[1/2,m+1](-1)^m2^(2m+1)}x^m ，m从0取到无穷大，比较B[x]的定义式，得出：b[n]= {[1/2,n+1](-1)^n2^(2n+1)}={(1/2)(1/2-1)(1/2-2)…(1/2-n)/(n+1)!}(-1)^n2^(2n+1)={(1/2)(1/2-1)(1/2-2)…(1/2-n)2^(n+1)(-1)^n/(n+1)!}2^n={1*3*…*(2n-1)/(n+1)!}2^n={1*2*3*4*…*(2n-1)*2n/(n+1)!}2^n/{2*4*…*2n}=2n!/(n+1)!/n!=(1/(n+1)){2n!/[n!n!]}=(1/(n+1))C(2n,n) 所以具有n个结点的二叉树具有互不相似的bn种形态，bn=(1/(n+1))C(2n,n)。 一棵一般的树可以转换成一棵没有右子树的二叉树，设具有n个结点的树具有互不相仿的tn种形态，那么t[n]=b[n-1]=(1/n)C(2n-2,n-1)。推导完毕。

评论