Catalan数以及相关性质的证明
Catalan数以及相关性质的证明
Catalan数的定义
给定一个凸n+1边形， 通过在内部不相交的对角线，把它划分成为三角形的组合，不同的划分方案的个数称为Catalan数，记作hn
比如说正对于五边形的Catalan数h4,可以可视化为下面的形式。
递推定义
分析
Catalan数的定义是描述一个凸多边形被不相交的直线分割为三角形的方案数，记这样一件事为A
创建确定一条边A1Ak+1
确定一个点B在上述边已经占用的其他边里面
左右两边的Catalan数的乘积是其整体的组合数
注意在这个解决A事件过程中，只需要定一条边就可以了，这是由于其他的边会由∑n−1l=1hkhn−k遍历得到，如果此时选择所有边，就会导致算出出现重复
依据递推方程求解Catalan数的解
牛顿二项式定理
∀α ∈R，且0≤|x|≤|y|，那么有:
(x+y)a=∑k=0∞(αk)xkya−k(αk)=α(α−1)(α−2)…(α−k+1)k!
现在计算(1+x)12的展开式
(1+x)12=∑k=0∞12(12−1)(12−2)…(12−k+1)k!xk=1+∑k=1∞(−1)k−11⋅3⋅5…(2k−3)2kk!xk=1+∑k=1∞(−1)k−1(2k−2)!2kk!⋅2k−1(k−1)!xk=1+∑k=1∞(−1)k−122k−1k(2k−2k−1)xk
Catalan数证明
设H(x)是Catalan数的生成函数
那么
H(x)=∑n=1∞hnxn
两边平方
H2(x)===∑n=1∞hnxn∑k=1∞hkxk∑n=1∞∑k=1∞hnhkxn+k∑n=2∞xn∑k=1n−1hkhn−k
由于
∑k=1n−1hkhn−k=hn
所以
H2(x)=∑n=2∞hnxn=H(x)−h1x
使用二次函数的求解得出
由于H(0)=0,过滤得出的解，故
H(x)=1−(1−4x)122………(1)
由于牛顿二项式展开定理
(1−4x)12=1+∑k=1∞(−1)k−122k−1k(2k−2k−1)(−4x)k
带入上式(1)
H(x)=∑n=1∞(−1)nn22n(2n−2n−1)(−1)nx2nxn=∑n=1∞1n(2n−2n−1)xn
故
hn=1n(2n−2n−1)
Python代码
import timedef combinatorial_number(m: int, n: int) -> int:
'''
:param n: 下标
:param m: 上标
:return: 返回组合数
'''
begin = n - m + 1
if m != 0:
result: int = int(factorial(begin=begin, end=n) / factorial(end=m)) else:
result: int = 1
return result passdef factorial(end: int, begin: int = 1) -> int:
result: int = begin if end != 0: for i in range(begin, end):
result *= i + 1
else:
result = 1
return result passdef catalan(num: int) -> int:
return int (combinatorial_number(n = 2 * num - 2, m = num - 1) / num)
t1 = time.time()for i in range(1, 11):
print("h{} = ".format(i), catalan(i))
t2 = time.time()
print("一共所花时间是{}".format(t2 - t1))h1 = 1h2 = 1h3 = 2h4 = 5h5 = 14h6 = 42h7 = 132h8 = 429h9 = 1430h10 = 4862一共所花时间是0.0005903244018554688
来源：https://www.cnblogs.com/mushrain/p/14770578.html