卡特兰数(Catalan Number)
卡特兰数(Catalan number) 其实来源于卡特兰解决凸n+2n+2n+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)=C2
卡特兰数(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=C2nn−C2nn−1
递推公式: f ( n ) = 4 n − 2 n − 1 f ( n − 1 ) f(n)=\frac{4n-2}{n-1}f(n-1) f(n)=n−14n−2f(n−1)
递归公式: 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(n−1)+f(1)∗f(n−2)+...+f(n−1)∗f(0)
接下来我们通过一系列的例子来深入理解一下卡特兰数。
走格子
走格子问题是对应卡特兰数的一个几何问题,可以从几何的角度来解释。
Description:
在 n ∗ n n*n n∗n的网格中,起始点为 ( 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) (n−1,n+1)。其实不管哪条不合法路径通过这条线对称过去,最终的终点都会变成 ( n − 1 , n + 1 ) (n-1,n+1) (n−1,n+1),所以说,所有的不合法路径都是唯一对应着一条到 ( n − 1 , n + 1 ) (n-1,n+1) (n−1,n+1)的路径,那么不合法的路径总数为 C 2 n n − 1 C_{2n}^{n-1} C2nn−1。那么合法的路径总数就为 C 2 n n − C 2 n n − 1 C_{2n}^{n}-C_{2n}^{n-1} C2nn−C2nn−1。 ==(通项公式)==
进出栈
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} C2nn−C2nn−1。 (通项公式)
与之相同分析方法的还有:
- 括号问题 , n n n个左括号, n n n个右括号,问有多少个长度为 2 n 2n 2n的括号序列使得所有的括号都是合法的。 (通项公式)
- 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,...,n−1,n利用进出栈来表示出来,312排列就是所有不能表示出来得排列,这个问题就转换成了进出栈问题,也是卡特兰数。 (通项公式) - 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} C2nn−C2nn−1。 (通项公式)
二叉树的构成问题
Description:
有 n n n个点,问用这 n n n个点最终能构成多少个不同的二叉树?
Answer:
这个问题使用的是 递归公式 推导的。
一个二叉树由根节点、左子树、右子树构成,左子树和右子树又是一个二叉树,并且左右子树的节点数之和为 n − 1 n-1 n−1。
我们假设 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(n−1)+f(1)∗f(n−2)+...+f(n−1)∗f(0),答案也是卡特兰数。
凸边形的剖分
Description:
求凸 n + 2 n+2 n+2边形用其 n − 1 n−1 n−1条对角线分割为互不重叠的三角形的分法总数。
Answer:
这个和上面那个二叉树的差不多。我们可以先随便连接两个顶点,这个凸多边形就会被划分为两个小的凸多边形,由于每条直线不能相交,那么这个凸多边形的方案数,就是两个小凸多边形的划分方案的乘积。
也是根据递推式推。
阶梯的矩形填充
用 n n n个长方形去填充一个高度为 n n n的阶梯图形的方法数。
我们可以看出每一个红色的小角肯定是属于不同的矩形。我们可以考虑一下与左下角那个紫色同属于一个矩形的是哪个角,假设是和第三个角属于一个矩形,那么这个矩形又将这个阶梯分成两个小梯形,这样就可以写出递推式了,所以所有的填充方案数就是卡特兰
f
(
n
)
f(n)
f(n)了。
![Logo](https://devpress.csdnimg.cn/79de2bf0b7994defa4242ef90d5513fa.jpg)
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
所有评论(0)