组合数学

组合数学是研究计数和排列组合的数学分支！从密码学到概率论，从算法设计到优化问题，组合数学无处不在。

什么是组合数学？

组合数学（Combinatorics）是研究离散对象的计数、排列、组合和结构的数学分支。

简单理解

组合数学就像"数数"：

• 有多少种方法排列对象？
• 有多少种方法选择对象？
• 有多少种方法组合对象？

排列

什么是排列？

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

排列数

从 $n$ 个不同元素中取出 $r$ 个元素的排列数：

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

例子：从 5 个人中选 3 个人排成一列，有多少种方法？

$P(5, 3) = 5 \times 4 \times 3 = 60$

全排列

$n$ 个不同元素的全排列数：

$P(n, n) = n!$

例子：3 个人排成一列，有 $3! = 6$ 种方法。

有重复元素的排列

如果 $n$ 个元素中有 $n_1$ 个相同、$n_2$ 个相同、……、$n_k$ 个相同，则排列数：

$\frac{n!}{n_1! n_2! \cdots n_k!}$

例子：单词 "MISSISSIPPI" 的字母有多少种排列？

$\frac{11!}{1! \times 4! \times 4! \times 2!} = \frac{39916800}{1152} = 34650$

组合

什么是组合？

组合（Combination）是从 $n$ 个不同元素中取出 $r$ 个元素，不考虑顺序。

组合数

从 $n$ 个不同元素中取出 $r$ 个元素的组合数（二项式系数）：

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

例子：从 5 个人中选 3 个人组成小组，有多少种方法？

$C(5, 3) = \frac{5!}{3!2!} = \frac{120}{12} = 10$

组合数的性质

对称性

$C(n, r) = C(n, n-r)$

递推关系

$C(n, r) = C(n-1, r-1) + C(n-1, r)$

这就是帕斯卡三角形（Pascal's Triangle）的递推关系。

二项式定理

$(x + y)^n = \sum_{r=0}^{n} C(n, r) x^{n-r} y^r$

例子：$(x + y)^3 = x^3 + 3x^2y + 3xy^2 + y^3$

计数原理

加法原理

如果完成一件事有 $m$ 种方法，完成另一件事有 $n$ 种方法，且两种方法互不重叠，则完成其中一件事有 $m + n$ 种方法。

乘法原理

如果完成一件事需要 $m$ 个步骤，第 $i$ 个步骤有 $n_i$ 种方法，则完成这件事有 $n_1 \times n_2 \times \cdots \times n_m$ 种方法。

例子：从 3 件上衣和 4 条裤子中选一套衣服，有多少种方法？

$3 \times 4 = 12$

容斥原理

容斥原理（Inclusion-Exclusion Principle）用于计算多个集合的并集的元素个数。

对于两个集合：

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

对于三个集合：

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

例子：在 100 个学生中，60 人学数学，50 人学物理，30 人两门都学，有多少人至少学一门？

$|M \cup P| = |M| + |P| - |M \cap P| = 60 + 50 - 30 = 80$

生成函数

什么是生成函数？

生成函数（Generating Function）是用幂级数表示序列的方法。

普通生成函数

序列 $\{a_n\}$ 的普通生成函数：

$G(x) = \sum_{n=0}^{\infty} a_n x^n$

应用

生成函数可以用于：

• 求解递推关系
• 计算组合数
• 证明恒等式

例子：$\{1, 1, 1, \ldots\}$ 的生成函数是 $\frac{1}{1-x}$

递推关系

什么是递推关系？

递推关系（Recurrence Relation）是用前面的项表示后面的项的公式。

线性递推关系

线性递推关系的形式：

$a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k} + f(n)$

求解方法

特征方程法

对于齐次线性递推关系 $a_n = c_1 a_{n-1} + c_2 a_{n-2}$：

1. 写出特征方程：$r^2 - c_1 r - c_2 = 0$
2. 求特征根 $r_1, r_2$
3. 根据根的情况写出通解

例子：斐波那契数列 $F_n = F_{n-1} + F_{n-2}$，$F_0 = 0$，$F_1 = 1$

• 特征方程：$r^2 - r - 1 = 0$
• 特征根：$r_1 = \frac{1+\sqrt{5}}{2}$，$r_2 = \frac{1-\sqrt{5}}{2}$
• 通解：$F_n = A r_1^n + B r_2^n$
• 代入初始条件，得到：$F_n = \frac{1}{\sqrt{5}} \left[\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n\right]$

组合数学的应用

计算机科学

• 💻 算法设计：动态规划、贪心算法
• 🔢 数据结构：树、图的结构
• 🔐 密码学：组合密码

概率论

• 📊 概率计算：计算事件的概率
• 🎲 随机过程：随机过程的分析

优化

• 📈 组合优化：旅行商问题、背包问题
• 🔍 搜索算法：搜索空间的分析

常见错误

错误 1：排列和组合混淆

• 排列：考虑顺序
• 组合：不考虑顺序

错误 2：计数原理使用错误

要正确使用加法原理和乘法原理。

错误 3：递推关系求解错误

要正确求解递推关系，注意初始条件。

小练习

1. 从 10 个人中选 5 个人排成一列，有多少种方法？
2. 从 10 个人中选 5 个人组成小组，有多少种方法？
3. 用容斥原理计算 $|A \cup B \cup C|$（已知 $|A|, |B|, |C|, |A \cap B|, |A \cap C|, |B \cap C|, |A \cap B \cap C|$）
4. 应用题：在密码学中，如何计算密码的可能组合数？

---

💡 小贴士：组合数学是研究计数和排列组合的数学分支。记住：排列考虑顺序，组合不考虑顺序。掌握组合数学，你就能解决许多计数问题！