卡特兰数 Catalan 数列 以下问题属于 Catalan 数列:
有 2n 个人排成一行进入剧场。入场费 5 元。其中只有 n 个人有一张 5 元钞票,另外 n 人只有 10 元钞票,剧院无其它钞票,问有多少种方法使得只要有 10 元的人买票,售票处就有 5 元的钞票找零? 一位大城市的律师在她住所以北 n 个街区和以东 n 个街区处工作。每天她走 2n 个街区去上班。如果他从不穿越(但可以碰到)从家到办公室的对角线,那么有多少条可能的道路? 在圆上选择 2n 个点,将这些点成对连接起来使得所得到的 n 条线段不相交的方法数? 对角线不相交的情况下,将一个凸多边形区域分成三角形区域的方法数? 一个栈(无穷大)的进栈序列为 1,2,3, \cdots ,n 有多少个不同的出栈序列? n 个结点可构造多少个不同的二叉树? n 个 +1 和 n 个 -1 构成 2n 项 a_1,a_2, \cdots ,a_{2n} ,其部分和满足 a_1+a_2+ \cdots +a_k \geq 0(k=1,2,3, \cdots ,2n) 对与 n 该数列为? 其对应的序列为:
H_0 H_1 H_2 H_3 H_4 H_5 H_6 ... 1 1 2 5 14 42 132 ...
(Catalan 数列)
递推式 该递推关系的解为:
H_n = \frac{\binom{2n}{n}}{n+1}(n \geq 2, n \in \mathbf{N_{+}}) 关于 Catalan 数的常见公式:
H_n = \begin{cases} \sum_{i=1}^{n} H_{i-1} H_{n-i} & n \geq 2, n \in \mathbf{N_{+}}\\ 1 & n = 0, 1 \end{cases} H_n = \frac{H_{n-1} (4n-2)}{n+1} H_n = \binom{2n}{n} - \binom{2n}{n-1} 例题洛谷 P1044 栈 题目大意:入栈顺序为 1,2,\ldots ,n ,求所有可能的出栈顺序的总数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14 // C++ Version
#include <iostream>
using namespace std ;
int n ;
long long f [ 25 ];
int main () {
f [ 0 ] = 1 ;
cin >> n ;
for ( int i = 1 ; i <= n ; i ++ ) f [ i ] = f [ i - 1 ] * ( 4 * i - 2 ) / ( i + 1 );
// 这里用的是常见公式2
cout << f [ n ] << endl ;
return 0 ;
}
# Python Version
f = [ 0 ] * 25
f [ 0 ] = 1
n = int ( input ())
for i in range ( 1 , n + 1 ):
f [ i ] = int ( f [ i - 1 ] * ( 4 * i - 2 ) // ( i + 1 ))
# 这里用的是常见公式2
print ( f [ n ])
路径计数问题 非降路径是指只能向上或向右走的路径。
从 (0,0) 到 (m,n) 的非降路径数等于 m 个 x 和 n 个 y 的排列数,即 \dbinom{n + m}{m} 。
从 (0,0) 到 (n,n) 的除端点外不接触直线 y=x 的非降路径数:
先考虑 y=x 下方的路径,都是从 (0, 0) 出发,经过 (1, 0) 及 (n, n-1) 到 (n,n) ,可以看做是 (1,0) 到 (n,n-1) 不接触 y=x 的非降路径数。
所有的的非降路径有 \dbinom{2n-2}{n-1} 条。对于这里面任意一条接触了 y=x 的路径,可以把它最后离开这条线的点到 (1,0) 之间的部分关于 y=x 对称变换,就得到从 (0,1) 到 (n,n-1) 的一条非降路径。反之也成立。从而 y=x 下方的非降路径数是 \dbinom{2n-2}{n-1} - \dbinom{2n-2}{n} 。根据对称性可知所求答案为 2\dbinom{2n-2}{n-1} - 2\dbinom{2n-2}{n} 。
从 (0,0) 到 (n,n) 的除端点外不穿过直线 y=x 的非降路径数:
用类似的方法可以得到: \dfrac{2}{n+1}\dbinom{2n}{n}
build 本页面最近更新: ,更新历史 edit 发现错误?想一起完善? 在 GitHub 上编辑此页! people 本页面贡献者:OI-wiki copyright 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用