第二个战场是组合。它问的问题朴素得可疑：到底有多少种？ 多少种排法、多少种选法、多少条路、多少种染色。
朴素归朴素，组合题最容易"数错"——要么数漏，要么数重。所以组合的全部功夫，就两个字：不重不漏。 这一章给你几把保证"不重不漏"的尺子。
一、两条原理：分类用加，分步用乘
数数的全部地基，是两条原理，名字吓人，意思是大白话：
- 加法原理（分类）：做一件事有几"类“互不相干的办法，总数就是各类相加。 从北京去上海，飞机有 3 班、高铁有 5 班——总共 \(3+5=8\) 种走法。 “或者这样、或者那样”，用加。
- 乘法原理（分步）：做一件事要连着走几”步"，每步有几种选择，总数就是各步相乘。 先从北京到南京（4 种），再从南京到上海（2 种）——总共 \(4\times2=8\) 种走法。 “先这样、再那样”，用乘。
一句口诀记牢：“或"用加，“且"用乘；分类相加，分步相乘。 八成的计数题，理清"这是分类还是分步”，就破了一半。
例 12.1（☼） 一个集合有 \(n\) 个元素，它有多少个子集（含空集和全集）？
别去一个个数子集，按"每个元素的去留"分步。组建一个子集，相当于对每个元素拍一次板：要它，还是不要它——2 种选择。\(n\) 个元素，就是连做 \(n\) 步、每步 2 选 1：
$$\underbrace{2\times2\times\cdots\times2}_{n\ \text{个}}=2^n.$$所以 \(n\) 元集合有 \(2^n\) 个子集。就这样。
把"选子集"翻译成"对每个元素做去留决定”，乘法原理立刻接管。计数题的关键一步，常常是把"数对象"翻译成"做一串决定"。
二、排列与组合：排队讲顺序，挑人不讲
两个最常用的计数量，先把名字脱了：
- 排列：从 \(n\) 个里取 \(k\) 个排成一队，讲先后顺序。第一位 \(n\) 选，第二位 \(n-1\) 选……共 \(n(n-1)\cdots(n-k+1)\) 种。
- 组合：从 \(n\) 个里挑一伙（一个小组），不讲顺序。记作 \(\binom{n}{k}\)，读作"\(n\) 选 \(k\)"。
组合和排列差在哪？差在"那 \(k\) 个挑出来后，排不排队"。同一伙 \(k\) 个人，能排出 \(k!\) 种队（第 1 章的阶乘），所以
$$\binom{n}{k}=\frac{\text{排列数}}{k!}=\frac{n(n-1)\cdots(n-k+1)}{k!}=\frac{n!}{k!\,(n-k)!}.$$不必死记这个分式，记住那个画面：先当排列排好队，再除掉"组内排队"的 \(k!\) 种重复。 这个"先多数、再除掉重复倍数"的思路，叫先污染后治理，组合里到处是它。
一个白送的对称（第 10 章）：\(\binom{n}{k}=\binom{n}{n-k}\)。挑出 \(k\) 个，等于挑出"剩下不要的" \(n-k\) 个——同一件事的两种说法。看见就能省算。
三、一一对应：数不清这个，就去数那个
组合里最漂亮的一招，叫一一对应（双射）：
想数 A 类东西有多少，可它不好数；要是能给 A 和某类好数的 B 配上一一对应的关系（A 的每个恰好对 B 的一个，不重不漏），那 A 的个数 = B 的个数，数 B 就行。
这招把"难数的"翻译成"好数的"，是组合的灵魂。
例 12.2（☼☼，方格路径） 在一张方格地图上，从左下角走到右上角，每步只能向右或向上走一格。若横向要走 \(m\) 格、纵向要走 \(n\) 格，问有多少条不同的路？
直接数路，岔来岔去数不清。做个对应：任何一条路，无非是一串"右、右、上、右、上……“的指令，总长 \(m+n\) 步，其中恰有 \(m\) 步是"右”、\(n\) 步是"上"。
反过来，任意排定"哪几步走右"，整条路就唯一定死了。于是——
$$\text{一条路}\quad\longleftrightarrow\quad\text{从 }m+n\text{ 步里挑出哪 }m\text{ 步走右}.$$这是一一对应。后者好数，就是 \(\binom{m+n}{m}\)。所以路的总数是 \(\binom{m+n}{m}\)。就这样。
我们没数一条路，只是把"数路"换成了"数选法"。碰到难数的对象，先问：它能不能跟某个好数的东西一一对上？
四、隔板法：相同的东西分进不同的盒
一类常见题：把 \(n\) 个一模一样的球，放进 \(k\) 个不同的盒子（允许空盒），有多少种放法？球都一样，按盒计数容易乱。
隔板法给个绝妙的对应：把 \(n\) 个球排成一行，要分进 \(k\) 个盒，等于在球的队伍里插 \(k-1\) 块隔板，隔板把球切成 \(k\) 段，依次倒进 \(k\) 个盒。于是
$$\text{一种放法}\ \longleftrightarrow\ \text{在 }n+k-1\text{ 个位置里，选 }k-1\text{ 个放隔板},$$答案就是 \(\binom{n+k-1}{k-1}\)。这又是一一对应在干活。（它正好回答"方程 \(x_1+x_2+\cdots+x_k=n\) 有多少组非负整数解"——每个 \(x_i\) 就是第 \(i\) 个盒里的球数。）
五、组合里别忘了前面的工具
组合战场上，第二部那几件工具照样常驻：
- 抽屉原理（第 4 章） 本就是组合的台柱，证"必有两个相同/相撞"。
- 染色 / 不变量（第 6 章） 管"能不能铺满/能不能达成"的组合构形题。
- 对称（第 10 章） 给你 \(\binom{n}{k}=\binom{n}{n-k}\) 这种省算，也支撑很多配对数法。
- 构造（第 9 章） 管"是否存在某种排法/染色"。
上手清单（计数题）
- 先分清：这是分类（用加）还是分步（用乘）？
- 讲顺序用排列，不讲顺序用组合（\(\binom nk\)）；重复了就"先污染后治理"，除掉重复倍数。
- 难数 → 找一一对应，翻译成好数的东西（选法、路径、隔板）。
- “必有两个相同/相撞” → 抽屉；“能不能铺满/达成” → 染色不变量。
这一章要带走的东西：
- 计数地基：分类相加，分步相乘（“或"加、“且"乘）。
- 排列讲顺序，组合不讲；组合 = 排列除掉组内的 \(k!\) 重复。
- 一一对应是灵魂：数不清这个，就配对去数那个（路径↔选法、放球↔隔板）。
- 组合战场上抽屉、染色、对称、构造照样当主力。
就这样。