如果你想攀登概率论的高峰，组合数学就是你脚下的山路。它不华丽，却是一切的基础。
引言：为什么要学组合数学？
想象一下：你面前有一副扑克牌，随机抽5张，恰好是同花顺的概率是多少？
要回答这个问题，你需要知道： - 一副牌有多少种可能的5张组合？ - 同花顺有多少种？ - 两个数字一除，就是答案
这就是组合数学的魔法——它教我们数数。
数数谁不会？但这里的关键是：在复杂的情况下，如何不重不漏地数清楚所有可能性。这不是简单的1+1=2，而是一种精妙的思维艺术。
概率论的本质是计数：\(P(A) = \frac{\text{事件A的情况数}}{\text{所有可能情况数}}\)
所以我说：组合数学是概率论的第一块基石。
第一章：最基本的计数法则
1.1 加法原理：走不同的路
加法原理：完成一件事有 \(n\) 类方法，每类方法分别有 \(a_1, a_2, \ldots, a_n\) 种方式，则完成这件事共有 \(a_1 + a_2 + \cdots + a_n\) 种方式。
比喻：你要从北京去上海，可以坐飞机（有5班）、坐高铁（有8班）、自驾（有3条路线）。一共多少种走法？
\(5 + 8 + 3 = 16\) 种。
关键点：这些方法是互斥的——你不能同时坐飞机又坐高铁。选了一种，就不能选另一种。
例子：从1-100中选一个数，是3的倍数或5的倍数，有多少个？
- 3的倍数：33个
- 5的倍数：20个
- 既是3又是5的倍数（15的倍数）：6个
注意！这里有重叠，不能直接33+20，需要用容斥原理（后面会讲）。
1.2 乘法原理：步步为营
乘法原理：完成一件事需要 \(n\) 个步骤，第一个步骤有 \(a_1\) 种方式，第二个步骤有 \(a_2\) 种方式，……，第 \(n\) 个步骤有 \(a_n\) 种方式，则完成这件事共有 \(a_1 \times a_2 \times \cdots \times a_n\) 种方式。
比喻：你要买一套衣服，上装有4种选择，下装有3种选择，鞋子有2种选择。一共有多少种全身搭配？
\(4 \times 3 \times 2 = 24\) 种。
关键点：这些步骤是依次进行的，每个步骤的选择不受其他步骤影响。
例子：用数字1、2、3、4、5能组成多少个三位数（各位数字可以重复）？
百位：5种选择（1-5） 十位：5种选择 个位：5种选择
\(5 \times 5 \times 5 = 125\) 个三位数。
1.3 加法与乘法的区别
| 场景 | 原理 | 核心区别 |
|---|---|---|
| 从A地到B地有3条路，从B地到C地有4条路 | 乘法原理 | 步骤相关联，要一步步走 |
| 从A地到C地，可以坐飞机或火车或汽车 | 加法原理 | 类别互斥，只能选一种 |
记住：先分类（加法）再分步（乘法），这是解决复杂计数问题的基本思路。
第二章：排列——顺序很重要
2.1 什么是排列？
排列（Permutation）：从 \(n\) 个不同元素中取出 \(r\) 个，按照一定顺序排成一列，记为 \(P_n^r\) 或 \(A_n^r\)。
公式： \[P_n^r = n \times (n-1) \times (n-2) \times \cdots \times (n-r+1) = \frac{n!}{(n-r)!}\]
其中 \(n! = n \times (n-1) \times \cdots \times 2 \times 1\)，叫做阶乘。
比喻：想象你有 \(n\) 个不同的座位，要安排 \(r\) 个人坐进去。第一个座位有 \(n\) 种选择，第二个座位有 \(n-1\) 种（已经坐了一个），以此类推。
例子：从5个人中选3个人排成一队，有多少种排法？
\(P_5^3 = 5 \times 4 \times 3 = 60\) 种。
2.2 全排列
当 \(r = n\) 时，叫做全排列： \[P_n^n = n!\]
例子：4个人排成一队，有 \(4! = 24\) 种排法。
有趣的应用——电话号码爆炸： 如果手机号码是11位，每位有10种选择（0-9），理论上可以有 \(10^{11} = 1000\) 亿个号码。中国14亿人，每人分10万个都够用——这就是号码资源”爆炸”的数学基础。
2.3 排列vs组合：到底区别在哪？
这是最容易混淆的概念。让我用一个生动的例子说明：
场景：从A、B、C、D四个人中选3个人
排列：选出3个人，还要排顺序 - 顺序ABC和顺序CBA是不同的！ - \(P_4^3 = 4 \times 3 \times 2 = 24\) 种
组合：选出3个人，不考虑顺序 - ABC和CBA是同样的！ - \(C_4^3 = \frac{4!}{3! \times 1!} = 4\) 种
一句话总结： > 排列看”顺序”，组合看”选择”
第三章：组合——只问结果，不问过程
3.1 什么是组合？
组合（Combination）：从 \(n\) 个不同元素中取出 \(r\) 个，不考虑顺序，记为 \(C_n^r\) 或 \(\binom{n}{r}\)。
公式： \[\binom{n}{r} = \frac{P_n^r}{r!} = \frac{n!}{r!(n-r)!}\]
理解：先按排列选出（有序），再除以 \(r!\)（去掉重复的顺序）。
例子：从5个人中选3个人组成一个委员会，有多少种选法？
\[\binom{5}{3} = \frac{5!}{3! \times 2!} = \frac{5 \times 4 \times 3}{3 \times 2 \times 1} = 10 \text{ 种}\]
3.2 组合数的性质
性质1：对称性 \[\binom{n}{r} = \binom{n}{n-r}\]
比喻：从10个人中选5个人去开会，等价于选5个人留下。两种选择方式的数量一样。
性质2： Pascal 递推公式 \[\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}\]
比喻：你要从 \(n\) 个人中选 \(r\) 个人。其中某个人A： - 选A：再从剩下 \(n-1\) 人中选 \(r-1\) 人 → \(\binom{n-1}{r-1}\) 种 - 不选A：从剩下 \(n-1\) 人中选 \(r\) 人 → \(\binom{n-1}{r}\) 种
这个性质揭示了组合数的递归结构，是后面学习生成函数的重要基础。
3.3 二项式定理
\[\binom{n}{0} + \binom{n}{1} + \binom{n}{2} + \cdots + \binom{n}{n} = 2^n\]
理解：对于 \(n\) 个元素，每个元素有”选”或”不选”两种状态，所以总共有 \(2^n\) 种选择。
例子： - \((a+b)^2 = a^2 + 2ab + b^2\) — 系数正好是 \(\binom{2}{0}, \binom{2}{1}, \binom{2}{2}\) - \((1+1)^2 = 2^2 = 4 = 1 + 2 + 1\) ✓
3.4 组合数的实际应用
例子1：扑克牌同花顺
- 一副牌52张，选5张：\(\binom{52}{5} = 2,598,960\) 种
- 同花顺：每种花色有10种（从A到10的顺子），4种花色，共40种
- 概率：\(40 / 2,598,960 \approx 0.0000154\)（约万分之一）
例子2：双色球
- 从33个红球中选6个：\(\binom{33}{6} = 1,107,568\) 种
- 从16个蓝球中选1个：\(\binom{16}{1} = 16\) 种
- 总组合：\(1,107,568 \times 16 = 17,721,088\) 种
- 中一等奖概率：约1772万分之一
第四章：容斥原理——处理重叠的艺术
4.1 问题的起源
场景：1到100中，是3的倍数或5的倍数的数有多少个？
- 3的倍数：\(\lfloor 100/3 \rfloor = 33\) 个
- 5的倍数：\(\lfloor 100/5 \rfloor = 20\) 个
- 直接相加：\(33 + 20 = 53\) 个
但这是错的！ 因为15、30、45…这些数被重复数了两次。
4.2 容斥原理
容斥原理（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|\]
比喻：想象你在整理一堆有重叠的拼图。直接数会重复，你需要： 1. 先全部加起来 2. 发现重叠了，减掉 3. 减多了？再加回来 4. 就像容斥一样，“包含-排除-再包含”，层层递进
4.3 容斥原理的例子
例子：1到1000中，能被3或5或7整除的数有多少？
解： - 能被3整除：\(\lfloor 1000/3 \rfloor = 333\) - 能被5整除：\(\lfloor 1000/5 \rfloor = 200\) - 能被7整除：\(\lfloor 1000/7 \rfloor = 142\)
能被3和5整除（15的倍数）：\(\lfloor 1000/15 \rfloor = 66\)
能被3和7整除（21的倍数）：\(\lfloor 1000/21 \rfloor = 47\)
能被5和7整除（35的倍数）：\(\lfloor 1000/35 \rfloor = 28\)
能被3、5、7同时整除（105的倍数）：\(\lfloor 1000/105 \rfloor = 9\)
应用容斥原理： \[333 + 200 + 142 - 66 - 47 - 28 + 9 = 543\]
答案是543个。
第五章：进阶组合数学
5.1 递推关系——递归的智慧
递推关系：通过已知的前几项来推导后面项的关系。
经典例子：斐波那契数列
\[F_n = F_{n-1} + F_{n-2}, \quad F_1 = 1, F_2 = 1\]
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …
比喻：就像兔子的繁殖——每一代的数量等于前两代数量的和。
实际应用：爬楼梯问题
问题：要爬10级楼梯，每次可以爬1级或2级，有多少种爬法？
解：设爬 \(n\) 级楼梯有 \(a_n\) 种方法 - 第一步爬1级，剩下 \(n-1\) 级：\(a_{n-1}\) 种 - 第一步爬2级，剩下 \(n-2\) 级：\(a_{n-2}\) 种
\[a_n = a_{n-1} + a_{n-2}\]
这不就是斐波那契数列吗！所以 \(a_{10} = 89\) 种。
5.2 生成函数——无声的求和
生成函数：把数列封装进一个”多项式”里，通过代数运算来研究数列的性质。
比喻：如果说递推关系是”显性基因”，那生成函数就是”隐性基因”——它把数列的结构编码在多项式的系数中，让复杂问题变得可以代数操作。
例子：求斐波那契数列的通项
设生成函数 \(F(x) = \sum_{n=0}^{\infty} F_n x^n\)
通过代数运算可以推导出： \[F_n = \frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n - \frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n\]
这就是著名的斐波那契数列通项公式，由数学家比内证明，也叫比内公式。
5.3 卡特兰数——优雅的平衡
卡特兰数（Catalan Number）：满足某些约束条件的序列计数。
通式： \[C_n = \frac{1}{n+1}\binom{2n}{n} = \frac{(2n)!}{(n+1)!n!}\]
前几项：1, 1, 2, 5, 14, 42, 132, 429, …
经典问题1：合法括号序列
\(n\) 对括号能组成多少种合法的表达式？
- 1对：() —— 1种
- 2对：()(), (()) —— 2种
- 3对：5种
- 这就是卡特兰数！
经典问题2：出栈序列
\(1, 2, 3, \ldots, n\) 按顺序入栈，有多少种不同的出栈序列？
答案也是卡特兰数 \(C_n\)。
经典问题3：二叉树
\(n+1\) 个叶子能构成多少种不同的二叉树？
答案还是卡特兰数 \(C_n\)！
比喻：卡特兰数就像”平衡”的数学化身——无论在括号、栈还是树的世界里，它总是悄然出现，守护着某种优雅的对称性。
5.4 整数分拆——数的分割艺术
整数分拆（Partition）：把一个正整数表示为若干个正整数之和，不考虑顺序。
例子：整数4有多少种分拆方式？
\[4\] \[3+1\] \[2+2\] \[2+1+1\] \[1+1+1+1\]
共5种。记作 \(p(4) = 5\)。
欧拉函数与分拆：数学家欧拉发现了一个惊人的事实——整数的分拆数量遵循极其复杂的规律，但可以通过生成函数来研究。
应用：在统计学、物理学（玻色-爱因斯坦凝聚）、计算机科学中都有重要应用。
第六章：排列组合的八大技巧
技巧1：特殊元素优先法
问题：6个人排成一排，甲必须在左边或右边，有多少种排法？
解： - 把甲放在最左边：其余5人全排列，\(5! = 120\) 种 - 把甲放在最右边：其余5人全排列，\(5! = 120\) 种 - 共 \(120 + 120 = 240\) 种
技巧2：捆绑法（相邻问题）
问题：6个人排成一排，甲、乙、丙三人必须相邻，有多少种排法？
解： - 把甲乙丙视为一个”整体”，与另外3人共4个元素全排列：\(4! = 24\) 种 - 甲乙丙内部再排列：\(3! = 6\) 种 - 共 \(24 \times 6 = 144\) 种
技巧3：插空法（不相邻问题）
问题：6个人排成一排，甲、乙、丙三人互不相邻，有多少种排法？
解： - 先排另外3人：\(3! = 6\) 种 - 产生4个”空位”（包括两端），甲乙丙插入这4个空位 - 从4个空位中选3个插入：\(\binom{4}{3} = 4\) 种 - 甲乙丙内部再排列：\(3! = 6\) 种 - 共 \(6 \times 4 \times 6 = 144\) 种
技巧4：隔板法（分配问题）
问题：把10个相同的球放入3个不同的盒子，每个盒子至少一个球，有多少种放法？
解：用隔板法 - 10个球有9个空隙 - 放2个隔板：\(\binom{9}{2} = 36\) 种
变式：如果盒子可以为空呢？ - 先每个盒子放1个”虚球”（共3个），变成13个球放3个盒子，每个至少一个 - \(\binom{12}{2} = 66\) 种
技巧5：逆向思维
问题：从1到1000中，不能被3、5、7整除的数有多少？
解：用容斥原理求能整除的，再用总数减去 - 能被3或5或7整除的：543个（见第四章例子） - 不能被整除：\(1000 - 543 = 457\) 个
技巧6：概率转化
问题：抛一枚硬币10次，恰好出现5次正面的概率是多少？
解： - 所有可能结果：\(2^{10} = 1024\) 种 - 恰好5次正面：\(\binom{10}{5} = 252\) 种 - 概率：\(252 / 1024 \approx 24.6\%\)
技巧7：分组与分配
问题：把6个人分成3组，每组2人，有多少种分法？
解： \[\frac{\binom{6}{2} \times \binom{4}{2} \times \binom{2}{2}}{3!} = \frac{15 \times 6 \times 1}{6} = 15 \text{ 种}\]
注意：为什么要除以 \(3!\)？因为组是无序的，\((A,B), (C,D), (E,F)\) 和 \((C,D), (A,B), (E,F)\) 是同一种分组。
技巧8：棋盘法（排列限制）
问题：3×3的棋盘，放3个相同的车（可以攻击同行同列），有多少种放法？
解：这等价于在3×3矩阵中选3个位置，使得没有两个在同一行或同一列——这就是排列问题：\(P_3^3 = 3! = 6\) 种。
结语：组合数学与概率论的桥梁
让我们回到文章开头的问题：
从一副扑克牌中抽5张，恰好是同花顺的概率是多少？
现在你可以自己算了： - 总的抽牌方式：\(\binom{52}{5} = 2,598,960\) - 同花顺：40种（A2345到10JQKA，4种花色） - 概率：\(40 / 2,598,960 \approx 0.0000154\)
这，就是组合数学的力量。
知识脉络总结
1 | ┌─────────────┐ |
组合数学不仅仅是数数，它是一种思维训练——教我们如何在复杂情况下保持清晰，如何处理重叠和重复，如何从局部推知整体。
这些思想方法，将伴随你整个概率论的学习之路。
本文是「概率论基础系列」的第一篇，后续我们将探讨概率空间、条件概率、随机变量等核心概念。敬请期待。