跳到主要内容

卡特兰数：一通百通

信息
2024年8月7日 · ·

卡特兰数（Catalan number）是一组自然数序列，以法国数学家欧仁·卡特兰命名，常用于组合数学中。它具有许多应用，包括栈排序问题、二叉树构造、括号匹配、路径计数等。

卡特兰数的第 (n) 项可以通过以下公式计算：

Cn=1n+1(2nn)=(2n)!(n+1)!n! C_n = \frac{1}{n+1} \binom{2n}{n} = \frac{(2n)!}{(n+1)!n!}

卡特兰数及其性质​

定义​

Cn=1n+1(2nn)=(2n)!(n+1)!n! C_n = \frac{1}{n+1} \binom{2n}{n} = \frac{(2n)!}{(n+1)!n!}

递推关系​

卡特兰数也可以通过递推关系来定义：

C∗0=1 C \ast 0 = 1 C∗n+1=∑∗i=0nCi⋅C∗n−i C \ast {n+1} = \sum \ast {i=0}^{n} C_i \cdot C\ast{n-i}

卡特兰数的应用​

卡特兰数在许多组合数学问题中出现，以下是一些经典的应用场景：

  1. 二叉树的结构：

    • 满二叉树（完全二分树）的数量：有 (n) 个内部节点的满二叉树有 (C_n) 种不同的结构。

  2. 合法括号序列：

    • 有 (n) 对括号的合法括号序列个数为 (C_n)。

  3. 凸多边形的三角剖分：

    • (n+2) 边凸多边形的三角剖分方式数为 (C_n)。

  4. 栈排序问题：

    • 长度为 (n) 的出栈顺序可能性的个数为 (C_n)。

  5. Dyck 路径：

    • 从 ((0, 0)) 到 ((n, n)) 不越过对角线的路径数为 (C_n)。

Python 实现卡特兰数​

下面是用 Python 计算卡特兰数的两种方法：直接公式和动态规划（递推关系）。

直接公式计算​

import math

def catalan_direct(n):
    return math.comb(2 * n, n) // (n + 1)

# 示例
print([catalan_direct(i) for i in range(10)])
# 输出：[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862]

递推关系实现​

def catalan_recursive(n):
    if n == 0:
        return 1
    catalan_numbers = [0] * (n + 1)
    catalan_numbers[0] = 1
    for i in range(1, n + 1):
        for j in range(i):
            catalan_numbers[i] += catalan_numbers[j] * catalan_numbers[i - 1 - j]
    return catalan_numbers[n]

# 示例
print([catalan_recursive(i) for i in range(10)])
# 输出：[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862]

一通百通​

卡特兰数体现了数学中许多问题的统一性和抽象的力量。通过研究卡特兰数及其证明，可以掌握解决一大类问题的技巧：

  1. 抽象建模： 学会将不同的问题抽象为同一类数学对象。例如，将二叉树、栈排序、括号匹配等问题统一到卡特兰数的问题范畴。

  2. 递推关系： 理解递推关系和动态规划的思维方式，卡特兰数的递推公式可以教会我们如何通过前一步的结果推导出下一步的结果。

  3. 组合计数： 熟悉组合数学中的基本工具和技巧，如组合数计算、递推公式和生成函数等，可以解决更多其他的组合计数问题。

通过卡特兰数的研究和应用，可以解决特定的组合计数问题，还能提升整体的数学思维和解决问题的能力，从而做到举一反三，一通百通。

PS：感谢每一位志同道合者的阅读，欢迎关注、点赞、评论！