Catalan数以及相关性质的证明

\(Catalan\) 数相关证明

\(Catalan\)数的定义

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

递推定义

分析

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

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

牛顿二项式定理

现在计算\((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 \dots\dots\dots(1)\]

使用二次函数的求解得出

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

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

由于牛顿二项式展开定理

\[\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