第 91 课 - 组合数学

学习目标

理解排列与组合的基本概念、公式，并能够计算相关问题。
掌握帕斯卡三角（杨辉三角）的生成方法及其与组合数的对应关系。
理解卡特兰数的定义、递推公式，并了解其在经典问题中的应用。
能够使用递归、递推等编程方法解决组合数学中的基础问题。

核心概念

想象一下，你有一个装满不同颜色小球的袋子。组合数学就是研究“如何选择”以及“如何排列”这些小球的学问。它是算法竞赛和实际编程中解决问题的重要工具。

排列 (Permutation)
- 是什么：从 n 个不同元素中，有顺序地选取 k 个元素排成一列。顺序很重要！例如，从{A, B, C}中选2个的排列，AB 和 BA 是两种不同的结果。
- 公式：P(n, k) = n! / (n-k)!。也可以理解为：第一个位置有 n 种选择，第二个位置有 n-1 种选择，...，第 k 个位置有 n-k+1 种选择，所以 P(n, k) = n * (n-1) * ... * (n-k+1)。
- 代码示例（计算排列数）：
```
def permutation(n, k):
    """计算排列数 P(n, k) = n! / (n-k)!"""
    if k < 0 or k > n:
        return 0
    result = 1
    # 等价于 n * (n-1) * ... * (n-k+1)
    for i in range(k):
        result = result * (n - i)
    return result

# 示例：从5个元素中选3个的排列数
print(f"P(5, 3) = {permutation(5, 3)}") # 输出: P(5, 3) = 60
```

组合 (Combination)

是什么：从 n 个不同元素中，不考虑顺序地选取 k 个元素组成一组。AB 和 BA 被视为同一种组合。
公式：C(n, k) = P(n, k) / k! = n! / (k! * (n-k)!)。组合数也常记作 C(n, k) 或 “n 选 k”。

代码示例（计算组合数）：

def combination(n, k):
    """计算组合数 C(n, k) = n! / (k! * (n-k)!)"""
    # 边界条件
    if k < 0 or k > n:
        return 0
    if k == 0 or k == n:
        return 1
    # 利用对称性 C(n, k) = C(n, n-k) 减少计算量
    k = min(k, n - k)
    result = 1
    # 使用迭代计算，避免大数阶乘
    for i in range(k):
        result = result * (n - i) // (i + 1)
    return result

# 示例
print(f"C(5, 3) = {combination(5, 3)}") # 输出: C(5, 3) = 10
print(f"C(100, 2) = {combination(100, 2)}") # 输出: C(100, 2) = 4950

帕斯卡三角 (Pascal‘s Triangle / 杨辉三角)

是什么：一个由数字排成的三角形，其中每个数是它左上方和右上方的数之和。它的第 n 行、第 k 列（从0开始计数）的数，恰好是组合数 C(n, k)。
性质：除了首尾是1，中间的数都满足 C(n, k) = C(n-1, k-1) + C(n-1, k)。这个性质是动态规划计算组合数的基础。

代码示例（生成帕斯卡三角）：

def generate_pascal_triangle(num_rows):
    """生成一个指定行数的帕斯卡三角"""
    triangle = []
    for i in range(num_rows):
        row = [1] * (i + 1) # 初始化每一行，两端都是1
        # 从第三个元素（索引1）开始，到倒数第二个元素
        for j in range(1, i):
            row[j] = triangle[i-1][j-1] + triangle[i-1][j]
        triangle.append(row)
    return triangle

# 打印帕斯卡三角的前5行
pascal_tri = generate_pascal_triangle(5)
for row in pascal_tri:
    print(row)

# 输出:
# [1]
# [1, 1]
# [1, 2, 1]
# [1, 3, 3, 1]
# [1, 4, 6, 4, 1]
# 注意：第4行（索引为3）的数字 [1,3,3,1] 对应 C(3,0)=1, C(3,1)=3, C(3,2)=3, C(3,3)=1。

卡特兰数 (Catalan Number)

是什么：一个数列，在组合数学中应用极广。其定义常通过递推式给出：C(0)=1, C(n+1) = Σ (C(i) * C(n-i))，其中 i 从 0 到 n。它也有一个显式公式 C(n) = C(2n, n) / (n+1)。
经典问题：n 对括号的合法序列数、n 个节点构成的不同二叉搜索树的数量、凸多边形三角剖分方案数、栈出栈序列数等等。

代码示例（计算卡特兰数）：

def catalan_number(n):
    """使用动态规划计算第n个卡特兰数"""
    # 创建一个数组来存储中间结果
    dp = [0] * (n + 1)
    dp[0] = 1  # 基础情况
    dp[1] = 1
    for i in range(2, n + 1):
        # 根据递推公式 C(i) = Σ (dp[j] * dp[i-1-j])
        for j in range(i):
            dp[i] += dp[j] * dp[i - 1 - j]
    return dp[n]

# 示例
for i in range(7):
    print(f"Catalan({i}) = {catalan_number(i)}")
# 输出:
# Catalan(0) = 1
# Catalan(1) = 1
# Catalan(2) = 2
# Catalan(3) = 5
# Catalan(4) = 14
# Catalan(5) = 42
# Catalan(6) = 132

代码示例

下面是一个综合示例，演示如何使用组合数生成所有长度为 n 的合法括号序列（卡特兰数的一个经典应用）。

def generate_parentheses(n):
    """
    生成所有有效的括号组合（卡特兰数应用）
    思路：使用回溯法。保证在添加过程中，左括号数量 >= 右括号数量。
    """
    result = []
    
    def backtrack(current, open_count, close_count):
        # 当前字符串长度达到2n，收集结果
        if len(current) == 2 * n:
            result.append(current)
            return
        
        # 如果左括号数量小于n，可以添加左括号
        if open_count < n:
            backtrack(current + '(', open_count + 1, close_count)
        
        # 如果右括号数量小于左括号数量，可以添加右括号
        if close_count < open_count:
            backtrack(current + ')', open_count, close_count + 1)
    
    backtrack("", 0, 0)
    return result

# 生成 n=3 的所有有效括号序列
valid_sequences = generate_parentheses(3)
print(f"当 n=3 时，共有 {len(valid_sequences)} 个有效序列（即第3个卡特兰数）：")
for seq in valid_sequences:
    print(seq)

输出：

当 n=3 时，共有 5 个有效序列（即第3个卡特兰数）：
((()))
(()())
(())()
()(())
()()()

实践练习

基础计算：编写一个函数 comb_mod(n, k, mod)，用于计算 C(n, k) % mod。当 n 和 k 较大时（例如 100000），直接计算阶乘会溢出，需要利用模逆元和费马小定理（mod 是质数）。可以参考组合数的递推公式 C(n, k) = C(n-1, k) + C(n-1, k-1) 进行动态规划求解。
生成三角：修改 generate_pascal_triangle 函数，使其返回一个由字符串组成的三角形，以便更美观地打印。例如，第3行应显示为 " 1 2 1 "（需要居中对齐）。尝试输入行数 num_rows = 7 并打印结果。
应用挑战：使用卡特兰数的思想，解决“n 个元素依次入栈，求所有可能的出栈序列数”的问题。请编写一个程序，输入 n，输出总方案数，并验证它与第 n 个卡特兰数是否一致。

常见错误

混淆排列与组合：误以为 C(n, k) 和 P(n, k) 是同一概念。记住关键区别：顺序是否重要。
递归计算组合数效率低下：直接使用公式 C(n, k) = C(n-1, k) + C(n-1, k-1) 的递归实现，会产生大量重复计算。应使用记忆化递归或动态规划（递推） 来优化。
整数溢出：当 n 很大时（如 n=30），n! 会超出 64 位整数的范围。解决方法有：1) 使用大数库；2) 在计算过程中取模（如果需要）；3) 使用帕斯卡三角的递推方式，逐行生成，避免直接计算阶乘。
卡特兰数公式应用错误：容易记混卡特兰数的显式公式 C(n) = C(2n, n) / (n+1)，注意这里是组合数 C(2n, n) 而不是 2n 个 n。

小结

本课我们学习了组合数学的几个核心概念：

排列与组合是计数的基石，分别对应“有序”和“无序”选取。
帕斯卡三角直观地展示了组合数 C(n, k) 的分布规律，并揭示了重要的递推关系。
卡特兰数是一类重要的数列，与众多经典的括号、树、路径计数问题紧密相连。
在编程实现时，应优先考虑使用动态规划（递推） 的方法来计算组合数和卡特兰数，以避免递归效率低和大数阶乘溢出的问题。

掌握这些知识，将为你解决许多涉及计数、枚举和优化的算法问题提供有力的数学工具。下一课，我们将进入概率与期望的领域。

练习编辑器

rust