原理
：
：
下面先证明问题2、3、4和问题1同解，再证明问题2、3、4的解是F(n)=C(2n,n)/(n+1)，从而证明问题1的解也是F(n)=C(2n,n)/(n+1)。
如果我们能证明问题2的解也可表示为F(n)=∑(k=0…n-1){F(k)*F(n-1-k)}，就完成了证明。
考虑n*n棋盘，记主对角线为L。从左下角走到右上角不穿过对角线L的所有路径，不算起点，一定有第一次接触到L的位置（可能是终点），设此位置为 M，坐标为(x,x)——设第一个数为横轴坐标。该路径一定从下方的(x,x-1)而来，而起点处第一步也一定是走向(1,0)，两者理由相同——否则就 穿过了主对角线。考虑从(1,0)到(x,x-1)的(x-1)*(x-1)的小
棋盘中，因为在此中路径一直没有接触过主对角线（M的选取），所以在此小棋盘中路径也一定没有穿过从(1,0)到(x,x-1)的小棋盘的对角线 L1。这样在这个区域中的满足条件的路径数量就是一个同构的子问题，解应该是F(x-1)，而从M到右上角终点的路径数量也是一个同构的子问题，解应该是 F(n-x)，而第一次接触到主对角线的点可以从(1,1)取到(n,n)，这样就有F(n)=∑(k=1…n){F(k-1)*F(n- k)}=∑(k=0…n-1){F(k-1)*F(n-k)}。证毕。
由以上可知问题1的解也是F(n)=C(2n,n)/(n+1)，故求和(k){F(k)*F(n-1-k)}=C(2n,n)/(n+1)。这个 数称为卡特兰数，前几项为1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796。
这里举个应用Catalan数的例子：n个节点能组成多少种形态的二叉树？（注：每个节点相同；形态不同的左右子树对调后形成的二叉树算新的形态的二叉树）
可以分析，当n=1时，只有1个根节点，则只能组成1种形态的二叉树，令n个节点可组成的二叉树数量表示为h(n)，则h(1)=1;
当n=2时，1个根节点固定，还有n-1个节点，可以作为左子树，也可以作为右子树，即：h(2)=h(0)*h(1)+h(1)*h(0)=2，则能组成2种形态的二叉树。这里h(0)表示空，所以只能算一种形态，即h(0)=1;
当n=3时，1个根节点固定，还有n-1=2个节点，可以在左子树或右子树，即h(3)=h(0)*h(2)+h(1)*h(1)+h(2)*h(0)=5，则能组成5种形态的二叉树。
以此类推，当n>=2时，可组成的二叉树数量为h(n)=h(0)*h(n-1)+h(1)*h(n-2)+…+h(n-1)*h(0)种，即符合Catalan数的定义，可直接利用通项公式(2)得出结果。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/210241.html原文链接：https://javaforall.net
