§1
计数是离散数学的核心技能：算法复杂度、概率模型、密码空间大小，最终都归结为"有多少种"。本章从加法与乘法两条原理出发，依次建立排列、组合、二项式系数、容斥原理与鸽笼原理，并强调计数问题的两条准线——是否有序与是否可重复。
一、两条基本原理
加法原理. 若完成一件事有 $k$ 类互不相交的方式，第 $i$ 类有 $n_{i}$ 种，则总数为 $n_{1}+n_{2}+\cdots+n_{k}$。对应集合语言：若 $A_{1},\dots,A_{k}$ 两两不交，则 $\lvert A_{1}\cup\cdots\cup A_{k}\rvert=\sum\lvert A_{i}\rvert$。
乘法原理. 若完成一件事需依次做 $k$ 个独立步骤，第 $i$ 步有 $n_{i}$ 种选择，则总数为 $n_{1}n_{2}\cdots n_{k}$，对应笛卡尔积的基数。
判别口诀："分类相加，分步相乘"。类与类之间必须互斥，步与步之间必须独立，否则会重复计数或漏算。
二、排列
从 $n$ 个不同元素中有序取出 $k$ 个（不放回），方案数为排列数
$$P(n,k)=n(n-1)\cdots(n-k+1)=\frac{n!}{(n-k)!}.$$
推理：第一位有 $n$ 种选择，第二位剩 $n-1$ 种……第 $k$ 位剩 $n-k+1$ 种，由乘法原理得积。特别地全排列 $P(n,n)=n!$，并约定 $0!=1$。
可重复排列. 若每次取后放回，长度 $k$ 的序列共 $n^{k}$ 个。例如 $8$ 位十进制密码有 $10^{8}$ 种。
圆排列. $n$ 个人围圆桌就座、旋转视为相同时，方案数为 $(n-1)!$（固定一人破除旋转对称）。
三、组合与二项式系数
从 $n$ 个不同元素中无序取出 $k$ 个，方案数为组合数
$$\binom{n}{k}=\frac{P(n,k)}{k!}=\frac{n!}{k!\,(n-k)!}.$$
除以 $k!$ 是因为同一个 $k$ 元子集对应 $k!$ 种排列顺序，而组合不计顺序。基本恒等式：
$$ \begin{align*} \binom{n}{k}&=\binom{n}{n-k},\\ \binom{n}{k}&=\binom{n-1}{k-1}+\binom{n-1}{k},\\ \sum_{k=0}^{n}\binom{n}{k}&=2^{n}. \end{align*} $$
第二式是帕斯卡递推，组合意义为：盯住某个特定元素，子集要么含它（余下从 $n-1$ 个里取 $k-1$ 个），要么不含它（从 $n-1$ 个里取 $k$ 个）。第三式即幂集大小，也说明杨辉三角每行之和为 $2^{n}$。
二项式定理.
$$(x+y)^{n}=\sum_{k=0}^{n}\binom{n}{k}x^{k}y^{n-k}.$$
展开 $n$ 个括号时每个括号选 $x$ 或选 $y$，选出 $k$ 个 $x$ 的方式恰有 $\binom{n}{k}$ 种，这就是系数的来源。令 $x=y=1$ 立得 $\sum_{k}\binom{n}{k}=2^{n}$。
| 情形 | 是否有序 | 是否可重复 | 计数公式 |
|---|---|---|---|
| 排列 | 有序 | 否 | $P(n,k)=n!/(n-k)!$ |
| 可重排列 | 有序 | 是 | $n^{k}$ |
| 组合 | 无序 | 否 | $\binom{n}{k}$ |
| 可重组合 | 无序 | 是 | $\binom{n+k-1}{k}$ |
四、容斥原理
两集合情形已见于第一章，三集合情形为
$$\lvert A\cup B\cup C\rvert=\lvert A\rvert+\lvert B\rvert+\lvert C\rvert-\lvert A\cap B\rvert-\lvert A\cap C\rvert-\lvert B\cap C\rvert+\lvert A\cap B\cap C\rvert.$$
一般地，对 $n$ 个集合
$$\Bigl\lvert\bigcup_{i=1}^{n}A_{i}\Bigr\rvert=\sum_{\varnothing\ne S\subseteq\{1,\dots,n\}}(-1)^{\lvert S\rvert+1}\Bigl\lvert\bigcap_{i\in S}A_{i}\Bigr\rvert.$$
思想是"加多了就减、减多了再加"：单独统计时重叠部分被重复计入，逐层用交集修正。求"一个性质都不满足"的个数时，用全集减去并集即可。
五、鸽笼原理
基本形式. 把 $n+1$ 个物体放入 $n$ 个盒子，必有某盒含至少 $2$ 个。
推广形式. 把 $N$ 个物体放入 $k$ 个盒子，必有某盒含至少 $\lceil N/k\rceil$ 个。证明用反证：若每盒都不超过 $\lceil N/k\rceil-1$ 个，总数不超过 $k(\lceil N/k\rceil-1) 使用鸽笼的关键是设计盒子：把待证结论中"必有两者相同或相关"的那个特征作为盒子的标签。它给出的是非构造性存在结论——断言存在却不指出是哪一个。
六、例题与解答
例题1（选委员会）
从 $10$ 人中选出 $4$ 人组成委员会。（a）共有多少种？（b）若甲必须入选，有多少种？（c）若还需从 $4$ 人中指定 $1$ 名主席，有多少种？
解：（a）无序选取，$\binom{10}{4}=\dfrac{10\cdot9\cdot8\cdot7}{4\cdot3\cdot2\cdot1}=210$ 种。
（b）甲已定，余下从 $9$ 人中选 $3$ 人：$\binom{9}{3}=\dfrac{9\cdot8\cdot7}{6}=84$ 种。
（c）先选人再指定主席：$210\times4=840$ 种；也可先选主席再选其余 $3$ 人：$10\times\binom{9}{3}=840$，两法一致。✓
例题2（容斥计数）
在 $1$ 到 $100$ 的整数中，有多少个能被 $2,3,5$ 中至少一个整除？多少个都不被整除？
解： 记 $A_{d}$ 为被 $d$ 整除的数集，$\lvert A_{d}\rvert=\lfloor 100/d\rfloor$：
$$\lvert A_{2}\rvert=50,\quad\lvert A_{3}\rvert=33,\quad\lvert A_{5}\rvert=20,$$
$$\lvert A_{2}\cap A_{3}\rvert=\lfloor100/6\rfloor=16,\quad\lvert A_{2}\cap A_{5}\rvert=10,\quad\lvert A_{3}\cap A_{5}\rvert=\lfloor100/15\rfloor=6,$$
$$\lvert A_{2}\cap A_{3}\cap A_{5}\rvert=\lfloor100/30\rfloor=3.$$
代入容斥得 $50+33+20-16-10-6+3=74$。故至少被一个整除的有 $74$ 个，一个都不被整除的有 $100-74=26$ 个。✓
例题3（鸽笼原理）
从 $1,2,\dots,10$ 中任取 $6$ 个不同的数，证明其中必有两数之和为 $11$。
解： 把十个数按"和为 $11$"配对成 $5$ 个盒子：
$$\{1,10\},\ \{2,9\},\ \{3,8\},\ \{4,7\},\ \{5,6\}.$$
取出的 $6$ 个数是鸽子，$5$ 个盒子是笼子，$6>5$，由鸽笼原理必有两个数落入同一盒，而同盒两数之和恰为 $11$。✓ 注意取 $5$ 个数时可以避免（每盒各取一个），所以 $6$ 是最小的保证值。
练习
1. 用 $26$ 个字母组成长度为 $4$ 的字符串，（a）允许重复、（b）不允许重复，各有多少种？
2. 求 $(x+2)^{5}$ 展开式中 $x^{3}$ 项的系数，并用帕斯卡递推验证 $\binom{8}{3}$。
3. $1$ 到 $60$ 中有多少个数既不被 $3$ 也不被 $4$ 整除？一年按 $12$ 个月计，至少多少人才能保证有两人生日同月？
参考答案.
1. （a）$26^{4}=456976$；（b）$P(26,4)=26\cdot25\cdot24\cdot23=358800$。
2. 通项 $\binom{5}{k}x^{k}2^{5-k}$，取 $k=3$ 得 $\binom{5}{3}\cdot2^{2}=10\times4=40$。又 $\binom{8}{3}=56$，而 $\binom{7}{2}+\binom{7}{3}=21+35=56$，递推成立。
3. $\lvert A_{3}\rvert=20$，$\lvert A_{4}\rvert=15$，$\lvert A_{12}\rvert=5$，并集 $=20+15-5=30$，故都不被整除的有 $60-30=30$ 个。生日问题需 $13$ 人：$12$ 人可能各占一个月，第 $13$ 人必与某人同月。
本章小结
- 分类相加、分步相乘是一切计数的起点，注意互斥与独立。
- 排列计顺序 $P(n,k)=n!/(n-k)!$；组合不计顺序 $\binom{n}{k}=n!/(k!(n-k)!)$。
- 二项式定理给出展开系数，帕斯卡递推生成杨辉三角。
- 容斥原理按交集层数正负交替修正重复计数。
- 鸽笼原理给出非构造性存在结论，成败取决于盒子的设计。
- 判别计数模型只需两问：有序否？可重复否？
本章互动演示见页面底部交互图（鸽笼原理演示 pigeonhole）。
互动演示
拖动下方控件观察动态过程。