第 5 章 · 计数与组合

组合数学回答「有多少种」:多少个密码组合、多少种排法、多少个满足条件的子集。它是概率论的底座(概率 = 期望情况数 ÷ 总情况数),也是算法复杂度分析的常备工具(数据结构课第 1 章的「操作次数」很多要靠它数)。本章从乘法原理出发,把排列、组合、鸽巢、容斥、二项式定理一网打尽,最后用几个真实密码学问题验证威力。

5.1 两大基本原理

乘法原理:一件事分 k 步,第 i 步有 nᵢ 种做法,总数 = n₁·n₂·…·n_k。加法原理:分几类互斥做法,各类数量相加。所有计数问题的第一动作:判断结构是「分步」还是「分类」(串行 = 乘,并列 = 加),口诀「分类相加,分步相乘」。判断错了,后面全错;练习时强制自己先写一句「这题是分步还是分类」。

5.2 排列与组合:取与排的四种情况

从 n 个不同元素取 k 个,按「是否排序」和「是否可重复」凑出四象限:

	有序	无序
不重复	排列 P(n,k) = n!/(n−k)!	组合 C(n,k) = n!/(k!(n−k)!)
可重复	nᵏ	C(n+k−1, k)(隔板法)

密码学实例:6 位数字密码共 10⁶ 种(可重复有序);5 张扑克牌的手牌 C(52,5) = 2,598,960(无序不重复)。
C(n,k) 的关键性质:对称性 C(n,k) = C(n,n−k);帕斯卡恒等式 C(n,k) = C(n−1,k−1) + C(n−1,k)(「含第 n 元素 + 不含」的分类,直接推导出杨辉三角,数据结构课第 5 章的动态规划雏形)。
隔板法(可重复无序,「n 种球取 k 个」):k 个球排一行,插 n−1 块板,答案 C(k+n−1, n−1)。经典应用:「10 个同样的糖果分给 3 个孩子」= C(12, 2) = 66。

组合恒等式的推导套路:构造一个计数场景,从两个角度数它。比如 Σ C(n,k) = 2ⁿ(第 1 章幂集的元素个数):n 个元素每个「选/不选」二选一;左边按「选几个」分类。同一对象两种数法,等式自证。

5.3 鸽巢原理:从「一定存在」到硬结论

鸽巢原理(抽屉原理):n+1 个物品放进 n 个盒子,必有盒子 ≥ 2 个。朴素但威力巨大,因为它给出无构造的存在性证明(第 4 章):

任意 13 人中,必有两人同月出生(13 物品,12 巢);
任意 5 个整数中,存在两个的差是 4 的倍数(按余数 0,1,2,3 分 4 巢,5 个整数必有两个同余,同余差可被 4 整除——第 9 章的同余在此预演);
300 人中必有 ≥ 2 人生日相同且性别相同(非生日差异……这类题的窍门是找对「巢」:巢 = 你要的「相同点」)。

一般化(强鸽巢):N 个物品进 n 个盒,必有盒 ≥ ⌈N/n⌉。「一个系 613 名学生,必有 ≥ ⌈613/366⌉ = 2 人同月同日生日」。

5.4 容斥原理:数「并集」的正负账本

直接数「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|(符号按「层次奇偶」交替:每层交集的系数 = (−1)^(层数+1))。经典应用:欧拉函数 φ(n)(1 到 n 中与 n 互素的个数)对质数幂的推导,以及「1 到 1000 中不能被 2、3、5 整除的数的个数」:

总数 1000 −(被 2 整除 500 + 被 3 整除 333 + 被 5 整除 200)+ (被 6 整除 166 + 被 10 整除 100 + 被 15 整除 66)− (被 30 整除 33)= 266。

(这个 266 正是 φ(2·3·5) 家族的骨架,第 9 章 RSA 选素数时你会再遇到容斥。)

5.5 二项式定理与组合身份

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

直观证明:展开 (a+b)ⁿ 时每个因子里「挑 a 还是 b」,k 个 b 的项数恰好是 C(n,k)。推论:aⁿ 各项系数和(令 a=b=1)= 2ⁿ;交错和(令 a=1, b=−1)= 0。二项式系数与杨辉三角(帕斯卡三角)同构,「第 n 行第 k 个 = C(n,k)」把代数恒等式变成几何直觉。二项式概率(n 次独立实验 k 次成功的概率 = C(n,k)pᵏ(1−p)^(n−k))是机器学习课第 5 章(贝叶斯)的前置。

常见错误

排列组合不分。「10 人互赠贺卡」(C(10,2),甲乙同卡)vs「10 人两两握手」(同 C)vs「10 人选正副班长」(P(10,2),有职级 = 有序);判断标准:交换两个元素,是同一种情况吗。
可重复性漏判。「6 位密码」每位可重(10⁶),「6 个不同字母排列」不可重(P);题目里的「不同」「可重复」是关键词。
容斥符号错。三层以上靠「层次计数」记符号(每层取反),别硬背;算时先画韦恩图定结构。
鸽巢题找错「巢」。巢 = 分类标准,要保证物品落入巢的依据无歧义(余数、月份、性别);找错巢,结论就不「必然」。

练习

手算:一个 8 位密码(大小写字母 + 数字,共 62 字符),至少含一个数字的组合总数(提示:总数 − 纯字母数,容斥/补集思想)。
手算:10 人围圆桌坐下,环形排列数(注意环形要除以 n 去旋转重复:9!)。再算其中 A、B 相邻的种数(捆绑法:把 AB 看成一个)。
动手:写程序验证帕斯卡恒等式:用递推打表 C(n,k)(n ≤ 20),随机抽 100 个 (n,k) 验证 C(n,k) = C(n−1,k−1) + C(n−1,k);再打印杨辉三角前 10 行。
思考:证明「任意 n+1 个不超过 2n 的正整数中,必有两个互质?」——先试,失败;再证「必有一个整除另一个」(按奇偶性剥 2 的幂分组)。体会「找对巢」需要的洞察从哪来(结构,不是运气)。