卡特兰数(Catalan number) 其实来源于卡特兰解决凸 n + 2 n+2 n+2边形的剖分问题得到的数列 f ( n ) f(n) f(n)(为了便于区分组合数,这里用 f ( n ) f(n) f(n)表示)。卡特兰数是组合数学中常出现在各种计数问题中的数列。

1 , 1 , 2 , 5 , 14 , 42 , 132... 1,1,2,5,14,42,132... 1,1,2,5,14,42,132...

卡特兰数的性质

通项公式: f ( n ) = C 2 n n n + 1 = C 2 n n − C 2 n n − 1 f(n)=\frac{C_{2n}^n}{n+1}=C_{2n}^n-C_{2n}^{n-1} f(n)=n+1C2nn=C2nnC2nn1

递推公式: f ( n ) = 4 n − 2 n − 1 f ( n − 1 ) f(n)=\frac{4n-2}{n-1}f(n-1) f(n)=n14n2f(n1)

递归公式: f ( n ) = f ( 0 ) ∗ f ( n − 1 ) + f ( 1 ) ∗ f ( n − 2 ) + . . . + f ( n − 1 ) ∗ f ( 0 ) f(n)=f(0)*f(n-1)+f(1)*f(n-2)+...+f(n-1)*f(0) f(n)=f(0)f(n1)+f(1)f(n2)+...+f(n1)f(0)

接下来我们通过一系列的例子来深入理解一下卡特兰数。

走格子

走格子问题是对应卡特兰数的一个几何问题,可以从几何的角度来解释。

Description:

n ∗ n n*n nn的网格中,起始点为 ( 0 , 0 ) (0,0) (0,0),终点为 ( n , n ) (n,n) (n,n)​,每次可以向右或者向上走一步,在任意一个时刻,往右走的次数要 ⩾ \geqslant ​​往上走的的次数。

Answer: 经过发现,所有合格路径否是不能触碰 y = x + 1 y=x+1 y=x+1这条直线的,只要碰到就说明这是一条不合法的路径。

下面我们从反面的角度分析,画一条不合法的路径(紫色的),然后把这条路径沿着 y = x + 1 y=x+1 y=x+1​​​对称过去,然后我们会发现,路径的终点变成了 ( n − 1 , n + 1 ) (n-1,n+1) (n1,n+1)​​​。其实不管哪条不合法路径通过这条线对称过去,最终的终点都会变成 ( n − 1 , n + 1 ) (n-1,n+1) (n1,n+1)​​​,所以说,所有的不合法路径都是唯一对应着一条到 ( n − 1 , n + 1 ) (n-1,n+1) (n1,n+1)​​​的路径,那么不合法的路径总数为 C 2 n n − 1 C_{2n}^{n-1} C2nn1​​​。那么合法的路径总数就为 C 2 n n − C 2 n n − 1 C_{2n}^{n}-C_{2n}^{n-1} C2nnC2nn1​​​。 ​==(通项公式)==

走格子

进出栈

Description:

给定一个栈,有 n n n​​次进栈, n n n次出栈,总共 2 n 2n 2n​次操作,问总共有多少合法的进出栈序列。

Answer:

其实我们可以知道,每一次进栈必须与一个出栈相对应,也就是说,在任何一个进出栈序列的 任意一个位置上,进栈的次数必须 ⩾ \geqslant 出栈的次数。

和上述的走格子方法是一样的,可以将进栈看作向右走一步,出栈是向上走一步,因此合法的进出栈序列个数为 C 2 n n − C 2 n n − 1 C_{2n}^{n}-C_{2n}^{n-1} C2nnC2nn1(通项公式)

与之相同分析方法的还有:

  1. 括号问题 n n n个左括号, n n n个右括号,问有多少个长度为 2 n 2n 2n的括号序列使得所有的括号都是合法的。 (通项公式)
  2. 312排列 ,一个长度为 n n n的排列 a a a,只要满足 i < j < k i<j<k i<j<k a j < a k < a i a_j<a_k<a_i aj<ak<ai,这个排列就称为312排列。求 n n n中全排列中不是312排列得排列个数。
    其实就是看一个排列 是否能用 1 , 2 , 3 , . . . , n − 1 , n 1,2,3,...,n-1,n 1,2,3,...,n1,n利用进出栈来表示出来,312排列就是所有不能表示出来得排列,这个问题就转换成了进出栈问题,也是卡特兰数。 (通项公式)
  3. 01序列 ,有 n n n个0, n n n个1,问有多少个长度为 2 n 2n 2n得序列,使得序列中的任意一个位置往前,1的个数$\geqslant$0的个数。 (通项公式)
圆内连弦

Description:

圆上有 2 n 2n 2n个点,以这些点为端点连互不相交的 n n n条弦,求连接的所有方法总数。

Answer:

我们规定start为起始点,顺时针方向为正方向。

从start开始,将一条弦 最先遇到的那个端点标记为 + + +,后来遇见的另一个端点为标记为 − - ,就可以得到如下图。

圆内连弦
对于标蓝的点来说,我们可以看出,在它之前, + + +号的标记是必须 ⩾ \geqslant − - 号的标记的。

这样一来,就又是上述问题同样的解法了, C 2 n n − C 2 n n − 1 C_{2n}^{n}-C_{2n}^{n-1} C2nnC2nn1(通项公式)

二叉树的构成问题

Description:

n n n个点,问用这 n n n​​个点最终能构成多少个不同的二叉树?

Answer:

这个问题使用的是 递归公式 推导的。

一个二叉树由根节点、左子树、右子树构成,左子树和右子树又是一个二叉树,并且左右子树的节点数之和为 n − 1 n-1 n1

我们假设 i i i个点可以构成 f ( i ) f(i) f(i)​个二叉树,那么 f ( i ) f(i) f(i)就是左右子树可以构成的二叉树个数的乘积。

那么 f ( n ) = f ( 0 ) ∗ f ( n − 1 ) + f ( 1 ) ∗ f ( n − 2 ) + . . . + f ( n − 1 ) ∗ f ( 0 ) f(n)=f(0)*f(n-1)+f(1)*f(n-2)+...+f(n-1)*f(0) f(n)=f(0)f(n1)+f(1)f(n2)+...+f(n1)f(0),答案也是卡特兰数。

凸边形的剖分

Description:

求凸 n + 2 n+2 n+2边形用其 n − 1 n−1 n1条对角线分割为互不重叠的三角形的分法总数。

Answer:

这个和上面那个二叉树的差不多。我们可以先随便连接两个顶点,这个凸多边形就会被划分为两个小的凸多边形,由于每条直线不能相交,那么这个凸多边形的方案数,就是两个小凸多边形的划分方案的乘积。

也是根据递推式推。

阶梯的矩形填充

n n n个长方形去填充一个高度为 n n n的阶梯图形的方法数。

在这里插入图片描述
阶梯的矩形填充
我们可以看出每一个红色的小角肯定是属于不同的矩形。我们可以考虑一下与左下角那个紫色同属于一个矩形的是哪个角,假设是和第三个角属于一个矩形,那么这个矩形又将这个阶梯分成两个小梯形,这样就可以写出递推式了,所以所有的填充方案数就是卡特兰 f ( n ) f(n) f(n)了。

Logo

开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!

更多推荐