组合数学

组合数学（Combinatorics）是研究离散结构的计数、存在性和优化问题的数学分支。它为算法复杂度分析、概率计算、密码学等领域提供了基础工具。从简单的排列组合到复杂的生成函数，组合数学贯穿于计算机科学的各个方面。

基本计数原理

加法原理

加法原理处理的是"或"的选择情况。如果完成一件事有 $n$ 类方法，第 $i$ 类方法有 $a_i$ 种具体方式，且各类方法之间互不重叠，那么完成这件事共有 $a_1 + a_2 + \cdots + a_n$ 种方法。

形式化表述：设 $A_1, A_2, \ldots, A_n$ 是互不相交的有限集合，则：

$|A_1 \cup A_2 \cup \cdots \cup A_n| = |A_1| + |A_2| + \cdots + |A_n|$

例子：从北京到上海可以坐飞机（3 个航班）、高铁（5 个车次）或汽车（2 个班次），共有 $3 + 5 + 2 = 10$ 种选择。

# 加法原理示例
flights = 3
trains = 5
buses = 2
total_choices = flights + trains + buses  # 10

乘法原理

乘法原理处理的是"且"的选择情况。如果完成一件事需要 $n$ 个步骤，第 $i$ 步有 $a_i$ 种选择方式，且各步骤相互独立，那么完成这件事共有 $a_1 \times a_2 \times \cdots \times a_n$ 种方法。

形式化表述：设 $A_1, A_2, \ldots, A_n$ 是有限集合，则：

$|A_1 \times A_2 \times \cdots \times A_n| = |A_1| \times |A_2| \times \cdots \times |A_n|$

例子：选择一套衣服，上衣有 4 件，裤子有 3 条，鞋子有 2 双，共有 $4 \times 3 \times 2 = 24$ 种搭配。

# 乘法原理示例
tops = 4
pants = 3
shoes = 2
total_outfits = tops * pants * shoes  # 24

正确选择计数原理

判断使用加法原理还是乘法原理，关键在于分清问题是"选择之一"还是"依次选择"：

• 加法原理：选择一种方式完成任务，各方式是"平行"关系
• 乘法原理：依次完成多个步骤，各步骤是"串行"关系

综合例子：从 5 本数学书和 4 本物理书中选择 2 本不同学科的书，有多少种选法？

分析：先选数学再选物理，或者先选物理再选数学。这是一个"分步选择"问题，但两步的顺序不同会导致不同的选择（数学书 A + 物理书 B 与 物理书 B + 数学书 A 是同一种选法）。正确分析是：选一本数学（5 种）和一本物理（4 种），共 $5 \times 4 = 20$ 种。

排列

排列的定义

从 $n$ 个不同元素中取出 $r$ 个元素，按照一定的顺序排成一列，称为从 $n$ 个元素中取 $r$ 个元素的排列（Permutation）。

排列强调顺序：$(a, b)$ 和 $(b, a)$ 是不同的排列。

排列数的计算

从 $n$ 个不同元素中取 $r$ 个元素的排列数记作 $P(n, r)$ 或 $A_n^r$：

$P(n, r) = \frac{n!}{(n-r)!} = n \times (n-1) \times \cdots \times (n-r+1)$

推导：第一个位置有 $n$ 种选择，第二个位置有 $n-1$ 种选择，依此类推，第 $r$ 个位置有 $n-r+1$ 种选择。根据乘法原理：

$P(n, r) = n \times (n-1) \times \cdots \times (n-r+1)$

特殊情况：当 $r = n$ 时，称为全排列，$P(n, n) = n!$

from math import factorial

def permutation(n, r):
    """计算 P(n, r)"""
    if r > n:
        return 0
    return factorial(n) // factorial(n - r)

# 从 5 个人中选 3 个人排成一列
print(permutation(5, 3))  # 60

排列的例子

问题：用数字 1, 2, 3, 4, 5 可以组成多少个没有重复数字的三位数？

解答：这是从 5 个元素中取 3 个的排列问题：$P(5, 3) = 5 \times 4 \times 3 = 60$ 种。

圆排列

将 $n$ 个不同元素排成一个圆圈，由于旋转不产生新的排列，圆排列数为：

$\frac{n!}{n} = (n-1)!$

理解：$n$ 个元素的直线排列有 $n!$ 种，但圆圈上旋转 $n$ 次回到原位，所以除以 $n$。

例子：4 个人围圆桌而坐，有 $(4-1)! = 6$ 种坐法。

组合

组合的定义

从 $n$ 个不同元素中取出 $r$ 个元素组成一个集合，不考虑顺序，称为从 $n$ 个元素中取 $r$ 个元素的组合（Combination）。

组合不强调顺序：$\{a, b\}$ 和 $\{b, a\}$ 是相同的组合。

组合数的计算

从 $n$ 个不同元素中取 $r$ 个元素的组合数记作 $C(n, r)$ 或 $\binom{n}{r}$：

$C(n, r) = \binom{n}{r} = \frac{n!}{r!(n-r)!} = \frac{P(n, r)}{r!}$

推导：先计算排列数 $P(n, r)$，再除以 $r!$（因为 $r$ 个元素的 $r!$ 种排列对应同一个组合）。

from math import factorial

def combination(n, r):
    """计算 C(n, r)"""
    if r > n or r < 0:
        return 0
    return factorial(n) // (factorial(r) * factorial(n - r))

# 从 5 个人中选 3 个人组成小组
print(combination(5, 3))  # 10

组合数的性质

对称性：

$\binom{n}{r} = \binom{n}{n-r}$

从 $n$ 个中选 $r$ 个，等价于从 $n$ 个中选 $n-r$ 个不选。

边界值：

$\binom{n}{0} = \binom{n}{n} = 1, \quad \binom{n}{1} = n$

递推关系（杨辉恒等式）：

$\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$

这是杨辉三角（帕斯卡三角）的构造原理。

def pascal_triangle(n):
    """生成杨辉三角的前 n 行"""
    triangle = []
    for i in range(n):
        row = [1] * (i + 1)
        for j in range(1, i):
            row[j] = triangle[i-1][j-1] + triangle[i-1][j]
        triangle.append(row)
    return triangle

# 打印前 6 行
for row in pascal_triangle(6):
    print(row)
# [1]
# [1, 1]
# [1, 2, 1]
# [1, 3, 3, 1]
# [1, 4, 6, 4, 1]
# [1, 5, 10, 10, 5, 1]

组合的例子

问题：一个班级有 30 名学生，要选出 3 名代表，有多少种选法？

解答：$C(30, 3) = \frac{30 \times 29 \times 28}{3 \times 2 \times 1} = 4060$ 种。

问题：一副扑克牌（52 张）中，任意抽取 5 张牌，有多少种可能？

解答：$C(52, 5) = \frac{52!}{5! \times 47!} = 2,598,960$ 种。

二项式定理

二项式定理的内容

二项式定理描述了二项式 $(a + b)^n$ 的展开式：

$(a + b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k = \binom{n}{0}a^n + \binom{n}{1}a^{n-1}b + \cdots + \binom{n}{n}b^n$

展开式中的系数 $\binom{n}{k}$ 正是组合数，也称为二项式系数。

例子：

$(a + b)^3 = a^3 + 3a^2b + 3ab^2 + b^3$

$(a + b)^4 = a^4 + 4a^3b + 6a^2b^2 + 4ab^3 + b^4$

二项式系数的组合意义

$\binom{n}{k}$ 表示从 $n$ 个元素中选 $k$ 个的组合数。在二项式展开中，它表示：

$(a + b)^n$ 的展开式中 $a^{n-k}b^k$ 项的系数，等于从 $n$ 个括号中选择 $k$ 个取 $b$（其余取 $a$）的方法数。

特殊情况

令 $a = b = 1$，得到：

$2^n = \sum_{k=0}^{n} \binom{n}{k} = \binom{n}{0} + \binom{n}{1} + \cdots + \binom{n}{n}$

这给出了一个组合解释：$n$ 元素集合的所有子集数（幂集的大小）等于各层组合数之和。

令 $a = 1, b = -1$，得到：

$0 = \sum_{k=0}^{n} (-1)^k \binom{n}{k} = \binom{n}{0} - \binom{n}{1} + \binom{n}{2} - \cdots$

这表明偶数位置的二项式系数之和等于奇数位置的二项式系数之和。

鸽巢原理

基本形式

鸽巢原理（Pigeonhole Principle）是一个简单却强大的存在性证明工具。

基本形式：如果 $n+1$ 只鸽子飞入 $n$ 个鸽巢，至少有一个鸽巢中有两只或更多鸽子。

一般形式：如果 $n$ 个物品放入 $m$ 个盒子，则至少有一个盒子中有 $\lceil n/m \rceil$ 个物品。

应用示例

问题：证明在任何 367 人中，至少有两人生日相同（假设一年 365 天）。

证明：将 367 人（鸽子）按生日放入 365 个"鸽巢"。由鸽巢原理，至少有一个生日对应 2 人以上。

问题：证明从 1 到 100 的整数中任取 51 个数，其中必有两个数互为倍数。

证明：每个正整数可以唯一表示为 $2^k \cdot m$，其中 $m$ 是奇数。1 到 100 中有 50 个不同的奇数 $m$。取 51 个数，由鸽巢原理，必有两个数对应相同的奇数 $m$，设为 $2^{k_1} \cdot m$ 和 $2^{k_2} \cdot m$。若 $k_1 < k_2$，则前者整除后者。

问题：证明在任意 6 个人中，必有 3 人互相认识或 3 人互不认识。

证明：任选一人 A，其余 5 人分为"认识 A 的"和"不认识 A 的"两组。由鸽巢原理，必有一组至少 3 人。假设"认识 A 的"组有 3 人 B、C、D。若 B、C、D 中有两人互相认识，加上 A 则有 3 人互相认识；若 B、C、D 两两不认识，则他们就是 3 人互不认识。

鸽巢原理的威力

鸽巢原理特别适合证明存在性问题。它不告诉你具体哪个鸽巢"拥挤"，但保证一定存在这样的鸽巢。

# 利用鸽巢原理检测重复元素
def find_duplicate(nums):
    """在 n+1 个范围 [1,n] 的数中找出重复的数"""
    # 鸽巢原理保证必有重复
    seen = set()
    for num in nums:
        if num in seen:
            return num
        seen.add(num)
    return None  # 理论上不会执行到这里

容斥原理

两个集合的容斥原理

对于两个集合 $A$ 和 $B$：

$|A \cup B| = |A| + |B| - |A \cap B|$

理解：直接相加会把交集中的元素数两次，需要减去一次。

三个集合的容斥原理

对于三个集合 $A$、$B$、$C$：

$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$

一般形式

对于 $n$ 个集合 $A_1, A_2, \ldots, A_n$：

$\left|\bigcup_{i=1}^{n} A_i\right| = \sum_{i}|A_i| - \sum_{i<j}|A_i \cap A_j| + \sum_{i<j<k}|A_i \cap A_j \cap A_k| - \cdots + (-1)^{n+1}|A_1 \cap A_2 \cap \cdots \cap A_n|$

应用示例

问题：在 1 到 100 的整数中，有多少个数不能被 2、3、5 任何一个整除？

解：设 $A$ 为被 2 整除的数，$B$ 为被 3 整除的数，$C$ 为被 5 整除的数。

$|A| = 50$，$|B| = 33$，$|C| = 20$

$|A \cap B|$ 是被 6 整除的数：$|A \cap B| = 16$

$|A \cap C|$ 是被 10 整除的数：$|A \cap C| = 10$

$|B \cap C|$ 是被 15 整除的数：$|B \cap C| = 6$

$|A \cap B \cap C|$ 是被 30 整除的数：$|A \cap B \cap C| = 3$

能被 2 或 3 或 5 整除的数：

$|A \cup B \cup C| = 50 + 33 + 20 - 16 - 10 - 6 + 3 = 74$

不能被任何一个整除的数：$100 - 74 = 26$

# 验证
count = sum(1 for i in range(1, 101) if i % 2 != 0 and i % 3 != 0 and i % 5 != 0)
print(count)  # 26

递推关系

递推关系的概念

递推关系是用前面的项来定义当前项的等式。它在算法分析中极为重要。

斐波那契数列是最经典的例子：

$F_n = F_{n-1} + F_{n-2}, \quad F_0 = 0, F_1 = 1$

汉诺塔问题

将 $n$ 个圆盘从柱 A 移到柱 C，每次只能移动一个圆盘，且大盘不能放在小盘上。

设移动 $n$ 个盘子的次数为 $T_n$。移动策略：

1. 将上面 $n-1$ 个盘子从 A 移到 B：$T_{n-1}$ 次
2. 将最大的盘子从 A 移到 C：1 次
3. 将 $n-1$ 个盘子从 B 移到 C：$T_{n-1}$ 次

递推关系：$T_n = 2T_{n-1} + 1$，$T_1 = 1$

解：$T_n = 2^n - 1$

def hanoi_moves(n):
    """计算 n 个盘子的最少移动次数"""
    return 2**n - 1

print(hanoi_moves(3))   # 7
print(hanoi_moves(10))  # 1023

递推关系的求解

线性齐次递推关系：形如 $a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k}$ 的递推关系。

求解方法：特征方程法。设 $a_n = r^n$，代入得到特征方程，求特征根，写出通解。

斐波那契数列的解：

特征方程：$r^2 = r + 1$，即 $r^2 - r - 1 = 0$

特征根：$r_1 = \frac{1+\sqrt{5}}{2}$，$r_2 = \frac{1-\sqrt{5}}{2}$

通解：$F_n = A \cdot r_1^n + B \cdot r_2^n$

代入初始条件 $F_0 = 0$，$F_1 = 1$，得：

$F_n = \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n\right]$

这就是著名的比内公式。

生成函数简介

生成函数的定义

对于数列 $\{a_n\}$，其生成函数（Generating Function）定义为形式幂级数：

$G(x) = \sum_{n=0}^{\infty} a_n x^n = a_0 + a_1 x + a_2 x^2 + \cdots$

生成函数将离散的数列转化为连续的函数，从而可以利用函数运算来解决计数问题。

常见数列的生成函数

常数列 $\{1, 1, 1, \ldots\}$：

$\sum_{n=0}^{\infty} x^n = \frac{1}{1-x}$

等比数列 $\{1, r, r^2, \ldots\}$：

$\sum_{n=0}^{\infty} r^n x^n = \frac{1}{1-rx}$

二项式系数 $\binom{n}{0}, \binom{n}{1}, \ldots, \binom{n}{n}$：

$(1+x)^n = \sum_{k=0}^{n} \binom{n}{k} x^k$

斐波那契数列：

$\sum_{n=0}^{\infty} F_n x^n = \frac{x}{1-x-x^2}$

生成函数的应用

问题：用 1 元、2 元、5 元硬币支付 $n$ 元，有多少种方法？

解：设方法数为 $a_n$，生成函数为：

$G(x) = (1 + x + x^2 + \cdots)(1 + x^2 + x^4 + \cdots)(1 + x^5 + x^{10} + \cdots)$

$= \frac{1}{1-x} \cdot \frac{1}{1-x^2} \cdot \frac{1}{1-x^5}$

展开后 $x^n$ 的系数即为 $a_n$。

def coin_ways(n):
    """计算用 1,2,5 元硬币支付 n 元的方法数"""
    ways = [0] * (n + 1)
    ways[0] = 1
    for coin in [1, 2, 5]:
        for i in range(coin, n + 1):
            ways[i] += ways[i - coin]
    return ways[n]

print(coin_ways(10))  # 10

小结

本章介绍了组合数学的基础知识：

1. 基本计数原理：加法原理（"或"的选择）、乘法原理（"且"的选择）
2. 排列与组合：排列强调顺序，组合不强调顺序
3. 二项式定理：$(a+b)^n$ 的展开式，系数为组合数
4. 鸽巢原理：证明存在性的有力工具
5. 容斥原理：计算并集大小的系统方法
6. 递推关系：用前面的项定义当前项
7. 生成函数：将离散数列转化为连续函数

组合数学是算法分析的基石。理解排列组合是分析排序算法复杂度的前提；鸽巢原理和容斥原理在概率计算中频繁出现；递推关系则是动态规划的理论基础。

练习

1. 计算 $P(8, 3)$ 和 $C(10, 4)$。

2. 一个委员会有 12 名成员，要选出 1 名主席、1 名副主席和 1 名秘书，要求 3 人不同，有多少种选法？

3. 用二项式定理展开 $(x + 2y)^4$。

4. 证明：在任意 $n+1$ 个正整数中，必有两个数之差能被 $n$ 整除。

5. 设 $a_n = 5a_{n-1} - 6a_{n-2}$，$a_0 = 1$，$a_1 = 4$。求 $a_n$ 的通项公式。