• 1
  • 2
  • 3
  • 4
  • 5
  • 6

Catalan数推导过程

零、前言

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)种。证毕。

点赞
  1. diziler说道:
    Google Chrome Windows 10
    Hi, Neat post. There is an issue with your site in internet explorer, would check thisK IE still is the market chief and a good part of folks will leave out your excellent writing because of this problem. Cherie Westbrook Asa
    1. 小竹同学 小竹同学说道:
      Google Chrome Windows 10
      sorry, I can't understand what your said, are you a robot or ADer?

发表评论

电子邮件地址不会被公开。必填项已用 * 标注