树的计数公式推导

首先提出树相似的定义，如果两棵树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]=1
b[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)。推导完毕。

评论