跳到主要内容

组合数学

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

什么是组合数学？​

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

简单理解​

组合数学就像"数数"：

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

排列​

什么是排列？​

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

排列数​

从 nn 个不同元素中取出 rr 个元素的排列数：

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

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

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

全排列​

nn 个不同元素的全排列数：

P(n,n)=n!P(n, n) = n!

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

有重复元素的排列​

如果 nn 个元素中有 n1n_1 个相同、n2n_2 个相同、……、nkn_k 个相同，则排列数：

n!n1!n2!⋯nk!\frac{n!}{n_1! n_2! \cdots n_k!}

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

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

组合​

什么是组合？​

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

组合数​

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

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

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

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

组合数的性质​

对称性​

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

递推关系​

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

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

二项式定理​

(x+y)n=∑r=0nC(n,r)xn−ryr(x + y)^n = \sum_{r=0}^{n} C(n, r) x^{n-r} y^r

例子：(x+y)3=x3+3x2y+3xy2+y3(x + y)^3 = x^3 + 3x^2y + 3xy^2 + y^3

计数原理​

加法原理​

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

乘法原理​

如果完成一件事需要 mm 个步骤，第 ii 个步骤有 nin_i 种方法，则完成这件事有 n1×n2×⋯×nmn_1 \times n_2 \times \cdots \times n_m 种方法。

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

3×4=123 \times 4 = 12

容斥原理​

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

对于两个集合：

∣A∪B∣=∣A∣+∣B∣−∣A∩B∣|A \cup B| = |A| + |B| - |A \cap B|

对于三个集合：

∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣A∩C∣−∣B∩C∣+∣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|

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

∣M∪P∣=∣M∣+∣P∣−∣M∩P∣=60+50−30=80|M \cup P| = |M| + |P| - |M \cap P| = 60 + 50 - 30 = 80

生成函数​

什么是生成函数？​

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

普通生成函数​

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

G(x)=∑n=0∞anxnG(x) = \sum_{n=0}^{\infty} a_n x^n

应用​

生成函数可以用于：

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

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

递推关系​

什么是递推关系？​

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

线性递推关系​

线性递推关系的形式：

an=c1an−1+c2an−2+⋯+ckan−k+f(n)a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k} + f(n)

求解方法​

特征方程法​

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

  1. 写出特征方程：r2−c1r−c2=0r^2 - c_1 r - c_2 = 0
  2. 求特征根 r1,r2r_1, r_2
  3. 根据根的情况写出通解

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

  • 特征方程：r2−r−1=0r^2 - r - 1 = 0
  • 特征根：r1=1+52r_1 = \frac{1+\sqrt{5}}{2}，r2=1−52r_2 = \frac{1-\sqrt{5}}{2}
  • 通解：Fn=Ar1n+Br2nF_n = A r_1^n + B r_2^n
  • 代入初始条件，得到：Fn=15[(1+52)n−(1−52)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∪B∪C∣|A \cup B \cup C|（已知 ∣A∣,∣B∣,∣C∣,∣A∩B∣,∣A∩C∣,∣B∩C∣,∣A∩B∩C∣|A|, |B|, |C|, |A \cap B|, |A \cap C|, |B \cap C|, |A \cap B \cap C|）
  4. 应用题：在密码学中，如何计算密码的可能组合数？

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