Catalan数以及相关性质的证明

\(Catalan\) 数相关证明

• Mushroom
• 2021-5-14

\(Catalan\)数的定义

给定一个凸\(n + 1\)边形， 通过在内部不相交的对角线，把它划分成为三角形的组合，不同的划分方案的个数称为\(Catalan\)数，记作\(h_n\)

比如说正对于五边形的\(Catalan\)数\(h_4\),可以可视化为下面的形式。

递推定义

分析

\(Catalan\)数的定义是描述一个凸多边形被不相交的直线分割为三角形的方案数，记这样一件事为\(A\)

graph LR
id1(创建确定一条边A1Ak+1)
id2(确定一个点B在上述边已经占用的其他边里面)
id1 –> id2
id4(左右两边的Catalan数的乘积是其整体的组合数)
id2 –> id4
id4 –> id2

注意在这个解决\(A\)事件过程中，只需要定一条边就可以了，这是由于其他的边会由\(\sum_{l=1}^{n-1}h_kh_{n-k}\)遍历得到，如果此时选择所有边，就会导致算出出现重复

依据递推方程求解\(Catalan\)数的解

牛顿二项式定理

\(\forall\)\(\alpha\) \(\in R\)，且\(0 \leq |x| \leq |y|\)，那么有:

\[(x + y)^a = \sum_{k = 0}^{\iNFTy}\begin{pmatrix}\alpha \\ k\end{pmatrix}x^ky^{a-k}\\
\begin{pmatrix}
\alpha\\
k
\end{pmatrix} = \frac{\alpha(\alpha – 1)(\alpha -2) \dots(\alpha -k + 1)}{k!}
\]

现在计算\((1 + x)^{\frac{1}{2}}\)的展开式

\[\begin{aligned}
(1 + x)^{\frac{1}{2}} = & \sum_{k=0}^{\infty}\frac{\frac{1}{2}(\frac{1}{2} – 1)(\frac{1}{2} -2)\dots (\frac{1}{2} – k + 1)}{k!}x^k
\\&=1 + \sum_{k = 1}^{\infty}\frac{(-1)^{k – 1}1 \cdot3\cdot5\dots(2k – 3)}{2^kk!}x^k
\\&=1 + \sum_{k=1}^{\infty}\frac{(-1)^{k-1}(2k-2)!}{2^kk!\cdot2^{k-1}(k-1)!}x^k
\\&=1 + \sum_{k=1}^{\infty}\frac{(-1)^{k-1}}{2^{2k-1}k}\begin{pmatrix}2k -2 \\ k-1\end{pmatrix}x^k
\end{aligned}
\]

\(Catalan\)数证明

设\(H(x)\)是\(Catalan\)数的生成函数

那么

\[H(x) = \sum_{n = 1}^{\infty}h_nx^n
\]

两边平方

\[\begin{aligned}
H^2(x) =& \sum_{n = 1}^{\infty}h_nx^n\sum_{k = 1}^{\infty}h_kx^k
\\=&\sum_{n=1}^{\infty}\sum_{k=1}^{\infty}h_nh_kx^{n+k}
\\=&\sum_{n=2}^{\infty}x^n\sum_{k=1}^{n-1}h_kh_{n-k}
\end{aligned}
\]

由于

\[\sum_{k=1}^{n-1} h_kh_{n-k} = h_n
\]

所以

\[H^2(x) = \sum_{n=2}^{\infty}h_nx^n = H(x) – h_1x
\]

使用二次函数的求解得出

由于\(H(0) = 0\),过滤得出的解，故

\[H(x) = \frac{1 – (1 -4x)^{\frac{1}{2}}}{2} \dots\dots\dots(1)
\]

由于牛顿二项式展开定理

\[\begin{aligned}
(1 – 4x)^{\frac{1}{2}} &= 1 + \sum_{k=1}^{\infty}\frac{(-1)^{k-1}}{2^{2k-1}k}\begin{pmatrix}2k -2 \\ k-1\end{pmatrix}(-4x)^k
\\&
\end{aligned}
\]

带入上式\((1)\)

\[\begin{aligned}
H(x) &= \sum_{n=1}^{\infty}\frac{(-1)^n}{n2^{2n}}\begin{pmatrix}2n -2 \\ n -1\end{pmatrix}(-1)^nx^{2n}x^n
\\&=\sum_{n=1}^{\infty}\frac{1}{n}\begin{pmatrix}2n -2 \\ n – 1\end{pmatrix}x^n
\end{aligned}
\]

故

\[h_n = \frac{1}{n}\begin{pmatrix}2n -2 \\ n – 1\end{pmatrix}
\]

Python代码

import time


def 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
    pass


def 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
    pass


def 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 =  1
h2 =  1
h3 =  2
h4 =  5
h5 =  14
h6 =  42
h7 =  132
h8 =  429
h9 =  1430
h10 =  4862
一共所花时间是0.0005903244018554688

PS

后续的一些应用场景以及性质会在慢慢更新的！！