【知识总结】卡特兰数 (Catalan Number) 公式的推导 |
您所在的位置：网站首页 › 卡特兰数公式的使用 › 【知识总结】卡特兰数 (Catalan Number) 公式的推导 |
【知识总结】卡特兰数 (Catalan Number) 公式的推导
|
卡特兰数的英文维基讲得非常全面，强烈建议阅读！
Catalan number - Wikipedia
(本文中图片也来源于这个页面) 由于本人太菜，这里只选取其中两个公式进行总结。 （似乎就是这两个比较常用？） 首先先扔卡特兰数的定义式 Catalann=∏i=1n−1Catalani∗Catalann−i C a t a l a n n = ∏ i = 1 n − 1 C a t a l a n i ∗ C a t a l a n n − i(卡特兰数的很多应用，比如二叉树形态数，出栈序列数等，都由这个定义式得到。详见英文维基) 公式1 (通项公式) ： Catalann=1n+1Cn2n C a t a l a n n = 1 n + 1 C 2 n n在上文提到的出栈序列的问题情景中，如果有
n
n
个元素，在平面直角坐标系中用xx坐标表示入栈数，
y
y
坐标表示出栈数，则坐标(a,b)(a,b)表示目前已经进行了
a
a
次入栈和bb次出栈，则再进行一次入栈就是走到
(a+1,b)
(
a
+
1
,
b
)
，再进行一次出栈就是走到
(a,b+1)
(
a
,
b
+
1
)
。并且，由于入栈数一定小于等于出栈数，所以路径不能跨越直线
y=x
y
=
x
因此，题目相当于求从
(0,0)
(
0
,
0
)
走到
(n,n)
(
n
,
n
)
且不跨越直线
y=x
y
=
x
的方案数 首先，如果不考虑不能跨越直线
y=x
y
=
x
的要求，相当于从
2n
2
n
次操作中选
n
n
次进行入栈，则方案数为Cn2nC2nn。 然后，考虑对于一种不合法的方案，一定在若干次操作后有一次出栈数比入栈数多一次，这个点在直线
y=x+1
y
=
x
+
1
(即下图中红色的线) 上。那么把第一次碰到该直线以后的部分关于该直线对称，则最终到达的点是
(n−1,n+1)
(
n
−
1
,
n
+
1
)
(如下图) 。 |
图源：英文维基 (即文首网址) 显然，任何非法方案都可以通过此方式变成一条从
(0,0)
(
0
,
0
)
到
(n−1,n+1)
(
n
−
1
,
n
+
1
)
的路径，有
Cn+12n
C
2
n
n
+
1
种。而任何合法方案由于不接触直线
y=x+1
y
=
x
+
1
，无论从哪个点对称都不是一条连续的路径。由于合法方案数就是
Catalann
C
a
t
a
l
a
n
n
，所以： 【本文地址】