卡特兰数
卡特兰数是组合数学中一个常出现于各种计数问题中的数列。其前几项为（从第0项开始）：1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, …
换句话说，如果你在做题时，手动模拟，发现是这样一串数时，就可以往卡特兰数上考虑。
n
n
n
个
0
0
0
和
n
n
n
个
1
1
1
，通过一系列的组合，组成一个长度为
2
n
2n
2
n
的序列，满足任意前缀中0的个数都不少于1的个数的序列数量为
C
a
t
n
=
C
2
n
n
n
+
1
Cat_n= \frac{C^n_{2n}}{n+1}
C
a
t
n
=
n
+
1
C
2
n
n
卡特兰数经典问题
1.火车进出栈问题
题目描述
n
n
n
个元素进栈序列为：
1
，
2
，
3
，
4
，
.
.
.
，
n
1，2，3，4，…，n
1
，
2
，
3
，
4
，
.
.
.
，
n
，则有多少种出栈序列。
问题分析：
如果将入栈设为用
0
0
0
代表，出栈用
1
1
1
代表，因为每个元素都要出栈，进栈，所以就有
n
n
n
个
0
0
0
，和
n
n
n
个
1
1
1
,而一个数只有先进栈才能出栈，所以这个问题就变成了，求
n
n
n
个
0
0
0
和
n
n
n
个
1
1
1
，通过一系列的组合，组成一个长度为
2
n
2n
2
n
的序列，满足
任意前缀
中0的个数都不少于1的个数的序列数量为。请注意这个任意前缀就限定了在前缀中
0
0
0
肯定在1的前面。例如如果
n
=
2
n=2
n
=
2
，排列顺序为
1010
1010
1
0
1
0
，其前缀
1
1
1
和前缀
101
101
1
0
1
不满足0的个数都不少于1的个数，但当排序为
0101
0101
0
1
0
1
时，任意前缀均满足0的个数都不少于1的个数。所以就将该问题抽象成了卡特兰数问题。
2.括号问题
题目描述
n
n
n
个左括号与
n
n
n
个右括号所组成的合法括号序列的数量为
C
a
t
n
=
C
2
n
n
n
+
1
Catn=\frac{C^n_{2n}}{n+1}
C
a
t
n
=
n
+
1
C
2
n
n
问题分析：
同理将左括号用
0
0
0
表示，右括号用
1
1
1
表示，每个左括号需要匹配一个右括号，并且只有有一个左括号才会有一个右括号，这就又抽象成了
n
n
n
个
0
0
0
和
n
n
n
个
1
1
1
，通过一系列的组合，组成一个长度为
2
n
2n
2
n
的序列，满足
任意前缀
中0的个数都不少于1的个数的序列数量，所以合法括号序列的数量为
C
a
t
n
=
C
2
n
n
n
+
1
Catn=\frac{C^n_{2n}}{n+1}
C
a
t
n
=
n
+
1
C
2
n
n
3.二叉树问题
n
n
n
个节点构成的不同二叉树的数量为
C
a
t
n
=
C
2
n
n
n
+
1
Catn=\frac{C^n_{2n}}{n+1}
C
a
t
n
=
n
+
1
C
2
n
n
这里的二叉树指的是满二叉树，及如果一棵二叉树的结点要么是叶子结点，要么它有两个子结点，这样的树就是满二叉树。
问题分析：
因为是满二叉树，所以每一个节点必有一个左子树和一个右子树，对于具有 n（ n>1 ）个结点的二叉树来说，都可以看成是一个根结点、由$ i$ 个结点组成的左子树和由$ n-i-1$ 个结点组成的右子树。因为在生成二叉树时，先生成左子树，再生成右子树，将左子树中的节点设为
0
0
0
，右子树中的节点设为
1
1
1
，而具有同一个父节点的左右节点是匹配的，这就与括号匹配和进出栈问题类似，所以可以用卡特兰数解决。
4.卡特兰数的几何意义
利用卡特兰数的几何意义解决问题：
[SCOI2010]生成字符串
总结
卡特兰数问题中都会存在一种匹配关系，如进出栈匹配，括号匹配等，一旦计数问题中存在这种关系，那我们就需要去考虑这是否是卡特兰数问题。此外，我们还可以记住序列前四项：
1, 1, 2, 5
，这些将有利于我们联想到卡特兰数。
卡特兰数练习题