第 6 章计数¶

章节导引

本页从《离散数学讲义》拆分而来，保留原章节锚点，方便从旧总览页和旧链接跳转。

学习目标¶

识别计数问题的对象、限制和是否允许重复，选择合适的排列组合模型。

前置知识¶

集合运算、函数概念、基础代数展开，以及能按条件拆分问题。

建议用时¶

建议 5–7 小时：基本原则 1 小时，排列组合 2–3 小时，二项式与广义模型 2–3 小时。

练习建议¶

各做 3 道加法/乘法原则、排列、组合题；解释每题为什么允许或不允许重复。

参考资料与引用边界¶

整理者：Lumner。
课程来源：根据 DM/ 目录下的课件整理；本章对应课件：DM6.1(3).pdf, DM6.2(3).pdf, DM6.3-6.4(6).pdf, DM6.5(3).pdf。
原始讲义文件：note/离散数学讲义.md。
引用边界：这是公开学习笔记，不替代课程正式教材、教师课件或考试要求；外部引用时请注明来自本网站整理版。

6.0 核心目标¶

计数研究“有多少种可能”。它是概率、算法分析、组合优化和离散结构枚举的基础。

本章重点：

乘法法则、加法法则、减法法则、除法法则。
鸽巢原理。
排列、组合和二项式系数。
允许重复、不可区分对象、盒子模型。

6.1 计数基础¶

乘法法则¶

若一个过程分为两个任务：

第一个任务有 \(n_1\) 种方式。
对每种第一任务的完成方式，第二个任务有 \(n_2\) 种方式。

则整个过程有 \(n_1n_2\) 种方式。

推广到 \(m\) 个阶段：

\(n_1n_2\cdots n_m\)

例：从 \(m\) 元集合到 \(n\) 元集合的函数数目为：

\(n^m\)

因为定义域中每个元素都有 \(n\) 种像的选择。

单射函数计数¶

从 \(m\) 元集合到 \(n\) 元集合的单射数目：

\(n(n-1)(n-2)\cdots(n-m+1)\)

前提是 \(m\le n\)。若 \(m>n\)，单射不存在。

幂集大小¶

若 \(|A|=n\)，则 \(|\mathcal P(A)|=2^n\)。

计数解释：每个元素都有“选入子集”和“不选入子集”两种选择，总共 \(2^n\) 种。

加法法则¶

若一个任务可以通过互不重叠的方式 A 或方式 B 完成，A 有 \(n_1\) 种，B 有 \(n_2\) 种，则总数为：

\(n_1+n_2\)

集合形式：若 \(A\cap B=\varnothing\)，则：

\(|A\cup B|=|A|+|B|\)

减法法则¶

若直接计数一个大集合容易，而坏情况也容易计数，则：

目标数 = 总数 - 不合法数。

例：长度 6 到 8 的密码，每位为大写字母或数字，且至少包含一个数字。

可按长度分别计数。长度为 \(k\) 时：

总数：\(36^k\)

全为字母：\(26^k\)

至少一个数字：\(36^k-26^k\)

所以总数：

\(\sum_{k=6}^8(36^k-26^k)\)

包含重叠时的加法¶

若两类方式有重叠：

\(|A\cup B|=|A|+|B|-|A\cap B|\)

例：不超过 100 且既不被 4 也不被 6 整除的正整数个数：

总数 100。

被 4 整除：\(\lfloor100/4\rfloor=25\)。

被 6 整除：\(\lfloor100/6\rfloor=16\)。

同时被 4 和 6 整除，即被 \(\operatorname{lcm}(4,6)=12\) 整除：\(\lfloor100/12\rfloor=8\)。

被 4 或 6 整除的数有 \(25+16-8=33\) 个。

目标为 \(100-33=67\)。

除法法则¶

若某个过程有 \(n\) 种执行方式，但每个最终结果都被重复计数了恰好 \(d\) 次，则不同结果数为：

\(n/d\)

除法法则常用于从排列推导组合。

树图¶

树图把每一步选择画成分支，叶子对应最终结果。它适合小规模分类计数，也能帮助检查分类是否遗漏或重叠。

6.2 鸽巢原理¶

基本鸽巢原理¶

若把 \(n+1\) 个对象放入 \(n\) 个盒子，则至少有一个盒子包含至少两个对象。

函数形式：若 \(|A|>|B|\)，则任意函数 \(f:A\to B\) 都不是单射。

例：同余¶

任取 11 个整数。它们除以 10 的余数只有 10 种。由鸽巢原理，至少有两个整数余数相同，所以它们的差能被 10 整除。

广义鸽巢原理¶

若 \(N\) 个对象放入 \(k\) 个盒子，则至少有一个盒子包含不少于：

\(\left\lceil\frac Nk\right\rceil\)

个对象。

等价地，若想保证某个盒子至少有 \(r\) 个对象，需要至少：

\(k(r-1)+1\)

个对象。

例：抽球¶

盒中有 10 个红球和 10 个蓝球。要保证至少抽到 3 个同色球，最多可先抽到 2 红 2 蓝而没有 3 个同色。再抽 1 个必然出现 3 个同色。

答案为 5。

整除链例题¶

在任意 \(n+1\) 个不超过 \(2n\) 的正整数中，必有一个数整除另一个数。

证明思路：每个正整数可写为 \(2^kq\)，其中 \(q\) 是奇数。\(1\) 到 \(2n\) 中奇数只有 \(n\) 个。把 \(n+1\) 个数按其奇数部分放入 \(n\) 个盒子，必有两个数奇数部分相同。它们形如 \(2^aq\) 和 \(2^bq\)，其中一个整除另一个。

单调子序列定理¶

任意 \(n^2+1\) 个不同整数构成的序列，必含有长度 \(n+1\) 的严格递增子序列或严格递减子序列。

证明常用鸽巢原理：对每个位置记录从该位置开始的最长递增子序列长度和最长递减子序列长度。若二者都不超过 \(n\)，则只有 \(n^2\) 种有序对，但有 \(n^2+1\) 个位置，产生矛盾。

六人朋友敌人问题¶

任意 6 个人中，若任意两人要么互为朋友要么互为敌人，则必存在 3 个互为朋友的人或 3 个互为敌人的人。

选定一人 A。A 与其他 5 人之间有朋友/敌人两种关系。由鸽巢原理，至少有 3 人与 A 同为朋友或同为敌人。若这 3 人之间存在一对关系与 A 同类，则与 A 组成三人同类；否则这 3 人彼此都是另一类，也组成三人同类。

6.3 排列与组合¶

排列¶

排列是对对象的有序安排。

从 \(n\) 个不同元素中取 \(r\) 个进行排列，数目为：

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

特别地，\(P(n,n)=n!\)。

例：8 个城市，起点固定，剩下 7 个城市任意访问，路线顺序数为 \(7!\)。

含指定字符串的排列¶

例：字母 ABCDEFGH 的排列中包含连续字符串 ABC 的有多少个？

把 ABC 看作一个整体，与 D,E,F,G,H 共 6 个对象排列，因此有 \(6!\) 种。

组合¶

组合是不考虑顺序的选择。

从 \(n\) 个元素中取 \(r\) 个，数目为：

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

因为每个 \(r\) 元集合对应 \(r!\) 个排列，所以组合数等于排列数除以 \(r!\)。

对称性¶

\(\binom nr=\binom n{n-r}\)

组合解释：选择 \(r\) 个留下，等价于选择 \(n-r\) 个不留下。

组合证明¶

组合证明是通过“同一对象用两种方式计数”证明恒等式。

例如 \(\binom nr=\binom n{n-r}\)：

左边数 \(n\) 个元素中选 \(r\) 个的方式，右边数选出被排除的 \(n-r\) 个的方式，二者一一对应。

6.4 二项式系数¶

二项式定理¶

对非负整数 \(n\)：

\((x+y)^n=\sum_{k=0}^n\binom nk x^{n-k}y^k\)

系数 \(\binom nk\) 来自选择 \(n\) 个因子中哪些提供 \(y\)。

例：求 \((2x-3y)^{25}\) 中 \(x^{12}y^{13}\) 的系数。

需要选 13 个因子提供 -3y，12 个因子提供 2x：

系数为：

\(\binom{25}{13}2^{12}(-3)^{13}\)

帕斯卡恒等式¶

\(\binom nk=\binom{n-1}{k-1}+\binom{n-1}{k}\)

组合解释：从 \(n\) 个元素中选 \(k\) 个，固定一个特殊元素 \(a\)。

选 \(a\)：还需从剩下 \(n-1\) 个中选 \(k-1\) 个。
不选 \(a\)：从剩下 \(n-1\) 个中选 \(k\) 个。

Vandermonde 恒等式¶

若 \(m,n,r\) 为非负整数，且 \(r\le m+n\)，则：

\(\sum_{k=0}^r\binom mk\binom n{r-k}=\binom{m+n}r\)

组合解释：从两个不相交集合 \(A,B\) 中总共选 \(r\) 个，按从 \(A\) 中选 \(k\) 个分类。

常见二项式恒等式¶

令 \(x=y=1\)：

\(\sum_{k=0}^n\binom nk=2^n\)

令 \(x=1,y=-1\)：

\(\sum_{k=0}^n(-1)^k\binom nk=0\)

所以偶数项组合数和等于奇数项组合数和：

\(\sum_{k\text{ even}}\binom nk=\sum_{k\text{ odd}}\binom nk=2^{n-1}\)

6.5 广义排列与组合¶

允许重复的排列¶

从 \(n\) 个对象中取 \(r\) 个，允许重复且考虑顺序，则有：

\(n^r\)

每个位置都有 \(n\) 种选择。

允许重复的组合¶

从 \(n\) 类对象中选 \(r\) 个，允许重复且不考虑顺序，数目为：

\(\binom{n+r-1}{r}=\binom{n+r-1}{n-1}\)

这就是 stars and bars 方法。

等价于非负整数解个数：

\(x_1+x_2+\cdots+x_n=r,\quad x_i\ge0\)

其解数为 \(\binom{n+r-1}{n-1}\)。

带下界的整数解¶

若：

\(x_1+x_2+\cdots+x_n=r,\quad x_i\ge a_i\)

令 \(y_i=x_i-a_i\ge0\)，则：

\(y_1+\cdots+y_n=r-\sum a_i\)

解数为：

\(\binom{r-\sum a_i+n-1}{n-1}\)

前提是 \(r-\sum a_i\ge0\)。

不可区分对象的排列¶

若共有 \(n\) 个对象，其中第 1 类有 \(n_1\) 个相同，第 2 类有 \(n_2\) 个相同，..., 第 \(k\) 类有 \(n_k\) 个相同，且：

\(n_1+n_2+\cdots+n_k=n\)

则不同排列数为：

\(\frac{n!}{n_1!n_2!\cdots n_k!}\)

盒子模型¶

计数问题常可理解为把对象放入盒子。

对象	盒子	是否允许空盒	常见公式
可区分	可区分	允许	\(k^n\)
可区分	可区分	指定每盒数量 \(n_i\)	\(\frac{n!}{n_1!\cdots n_k!}\)
不可区分	可区分	允许	\(\binom{n+k-1}{k-1}\)
可区分	不可区分	不允许空盒	Stirling 数 \(S(n,k)\)

Stirling 数¶

\(S(n,j)\) 表示把 \(n\) 个可区分对象分成 \(j\) 个非空、不可区分盒子的方式数。也就是把 \(n\) 元集合划分为 \(j\) 个非空子集的数目。

常用递推：

\(S(n,j)=jS(n-1,j)+S(n-1,j-1)\)

解释：

第 \(n\) 个元素放入已有 \(j\) 个盒子之一：\(jS(n-1,j)\)。
第 \(n\) 个元素单独成新盒子：\(S(n-1,j-1)\)。

本章小结与后续扩展¶

本章已覆盖基础计数、鸽巢原理、排列组合、二项式系数和广义组合。后续可补充更多“限制条件计数”题型，如相邻限制、圆排列、错排与容斥的连接。

第 6 章 计数¶