🧮 CSC3001 LEC14-16 Binomial and IE Principles, Pigeonhole Theorem

November 13, 2025

(涵盖第 12 个讲义)

LN12

记 $\displaystyle{n\choose k}$ 为从 n 个互异元素里选 k 个的方式数（“从 n 里挑 k”）。
代数定义：$\displaystyle{n\choose k}=\frac{n!}{k!(n-k)!}$，并约定 ${n\choose 0}={n\choose n}=1$。
组合解释（极其重要）：每个 ${n\choose k}$ 就是一类“从 n 个位置里挑 k 个位置”的计数问题。
常见推理思路： 1、直接数学证明：LHS = RHS； 2、利用组合数与二项式的内在关联转换问题：比如 $\sum_{i=0}^n{n\choose i}^2={2n\choose n}$ 可以利用 (x+1)ⁿ(x+1)ⁿ = (x+1)²ⁿ 这个二项式等式左右的 xⁿ 项系数相等证明； 3、举例证明：想象为袋中选球。

$$(1+x)^n=\sum_{k=0}^{n}{n\choose k}x^k.$$

组合证明：把 $(1+x)^n$ 看作 n 个因子 (1+x) 的乘积；从每个因子里选“1”或“x”。系数 x^k 等于从 n 个因子里选出 k 个放“x”的方式数——正是 ${n\choose k}$。

取 x=1：$\displaystyle \sum_{k=0}^n{n\choose k}=2^n$。组合解释：子集计数（每个元素取或不取）。
取 x=-1：$\displaystyle \sum_{k\ \text{偶}}{n\choose k}=\sum_{k\ \text{奇}}{n\choose k}=2^{n-1}$。组合解释：把每个子集与其补集配对，偶数大小与奇数大小一样多。
${n\choose k}={n\choose n-k}.$

$${n+1\choose k}={n\choose k-1}+{n\choose k}.$$

组合证明：在 n+1 中固定一个元素 x，去掉 x 留下 n 个元素。如果 x 不在 k 中，就仍然从 n 中选 k 个；如果 x 在 k 中，就只能选 k-1 个元素，为被去掉的 x 预留位置。（或者直接拆开计算，LHS = RHS）

$$\sum_{i=r}^{n}{i\choose r}={n+1\choose r+1}.$$

组合证明：从 {1, …, n+1} 里选 r+1 个元素，按“最大元素 λ”分类（λ ∈ [r+1, n+1]），除了最大项 λ 以外的 r 个元素从 1 到 λ-1 里随便选——得到 ${λ-1\choose r}$，对 λ 求和即得证。

$$\sum_{i=0}^{k}{r\choose i}{s\choose k-i}={r+s\choose k}.$$

组合证明：把 r+s 个元素分两堆（大小 r,s），总体选 k 个；按“从第一堆取 i 个、第二堆取 k-i 个”分类求和。

$$(k+1){n\choose k+1}=(n-k){n\choose k},\qquad k{n\choose k}=n{n-1\choose k-1}.$$

组合证明（第二式）：先从 n 人里选一位“队长”再选其余 k-1 人；或先定 k 人小队再在队内定队长。

$$\sum_{k=0}^n k{n\choose k}=n2^{,n-1},\quad \sum_{k=0}^n k(k-1){n\choose k}=n(n-1)2^{,n-2}.$$

容斥原理：用交集求并集 $|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|.$

使用例：计算 1000 以内能被 x 或 y 整除的数的个数 $⌊{1000\over x}⌋+⌊{1000\over y}⌋-⌊{1000\over lcm(x, y)}⌋$

$$\Big|\bigcup_{i=1}^n A_i\Big| =\sum_{t=1}^n(-1)^{t-1}!!\sum_{1\le i_1<\cdots<i_t\le n} \left|A_{i_1}\cap\cdots\cap A_{i_t}\right|.$$

你可以这么理解：每个元素若落在 m 个集合里，就被计了 $\sum_{t=1}^{m}(-1)^{t-1}{m\choose t}=1$ 次。

错排 D_n：n 个人每人提供一件礼物，随机抽取时没有人拿到自己的礼物的情况：假设“第 i 个人拿到自己的礼物”记作 M_i：$D_n = |\bigcap_{i=1}^n\bar M_i|=|Ω|-|\bigcup_{i=1}^n M_i| =n!+\sum_{i=1}^n (-1)^i{n \choose i}(n-i)!=n!\sum_{i=0}^n\frac{(-1)^i}{i!};$ 概率 $P=\frac{D_n}{n!}=\sum_{i=0}^n\frac{(-1)^i}{i!}(n\to \infty)\to e^{-1}.$
Euler φ(n) 函数：小于 n 并与它互素的正整数的个数。假设 n 可分解为一些质因数次方的乘积：$n=\prod p_i^{c_i}$，将“一个 [1, n] 中的数可以被 pi 整除”记作 D_i： $\varphi(n) = |\bigcap_{i=1}^n\bar D_i|=n-|\bigcup_{i=1}^n D_i|;$ $\varphi(n)=n\prod(1-\frac1{p_i}).$
非负整数解（隔板法 + 容斥约束） a+b+c=11 且 P: 0≤a≤3、Q: 0≤b≤4、R: 0≤c≤6 有多少解? |P∩Q∩R| = |Ω| - |P_c∪Q_c∪R_c|
- 先算无约束情况下的全集 |Ω| = ${11+2\choose 2}$ (隔板法：11 个球和 2 个板占据 13 个空间，有多少放法？)
- 计算所有容斥项：|Pc| = ${13-4 \choose 2}$；|Pc∪Qc| = ${13-4-5 \choose 2}$；|Pc∩Qc∩Rc| = 0；……
- 最后就可以算出：|P∩Q∩R| = 78-36-28-15+6+1+0-0 = 6

解题思路：

配对求和：证明从 {1, …, 8} 选 5 个元素，必有一对和为 9。洞是含有两个元素和为 9 的集合：{1,8},{2,7},{3,6},{4,5}。在 4 个集合选 5 个数 ⇒ 必有某个集合被选 2 次 ⇒ 得到一对和为 9。

握手问题：证明 n 个人随便互相握手，必有两人与相等个数的人握手。将握手问题看作图论，洞是所有可能的度数：n 人各自的度数∈ {0, …, n-1}； (1) 若有人度数 0，则没人能是 n-1；于是 n 人在 {0, …, n-2} 中选度数：⌈n / n-1⌉ = 2 ⇒ 必有两人度数相同。 (2) 若无人不握手，则 n 人在 {1, …, n-1} 中选度数：⌈n / n-1⌉ = 2 ⇒ 必有两人度数相同。 Takeaway：可以通过分类讨论减少“洞”，让其小于“鸽子”

生日悖论：n 个人没有重复生日的概率。 $P(n) = \frac{无重复选法}{随机选法} = \frac{365\cdot 364\cdots(365-n+1)}{365^n}$，P(23) < 0.5。

和/差/倍数类问题：任取 n+1 个数于 {1, …, 2n}，必有一对整除另一对。把每个数分解成唯一的 $2^t\cdot q$ (q 为奇数)；在 1～2n 中共有 {1, 3, …, 2n-1} 也就是 n 个奇数；按 q 的可能取值构造 n 个洞，则 n+1 个数在 n 个奇数因子中选一个：⌈n+1 / n⌉ = 2 ⇒ 必有两数为偶倍数。 Takeaway：本题也可以用欧拉函数做，但可能要用黎曼 ζ 函数来定量质数的个数

子集和不可能全不同：90个 25 位十进制数组成的集合，必有两个子集和相等。子集数 2⁹⁰（鸽子）> 和的取值个数 9x10²⁶（洞），故存在两子集同和。