零、前言
Catalan数应用非常广泛,在很多递归背景的数学应用中经常看到,常见的有矩阵链乘问题、栈的进出问题、凸边形三角形问题、蚂蚁问题等等。下面主要记录我自己的推导过程。
一、推导
下面推导以二叉树形态问题为例,主要目的是为了推出递归格式。
(1)当只有一个结点时。设为f(1)=1。
(2)当只有两个结点时。固定根节点,剩下有1个结点,分别能放在左子树和右子树,f(2)=1+1=2。
(3)当只有三个结点时。固定根节点,剩下有两个结点。有三种情况:①2个结点全部放左边,有f(2)种。②2个结点一个放左边,一个放右边,为f(1)×f(1)种。③2个结点全部放右边,有f(2)种。
(4)当只有k个结点时。固定根节点,剩下有k-1个结点。有k种情况:①k-1个结点全部放在左边,有f(k-1)种。②k-1个结点k-2个放左边,1个放右边,有f(k-2)*f(1)种。(此处省略。。。)。
由数学归纳法可得,当有n个结点时,共有f(n-2)*f(1)+f(n-3)*f(2)+...+f(2)*f(n-3)+f(1)*f(n-2)种。证毕。