组合计数
这一页教你系统回答”有多少种”这类问题：从加法、乘法原理两块最基本的砖出发，推出排列数与组合数公式，再用二项式定理、容斥原理、鸽巢原理和隔板法四类工具处理带约束的计数。学完之后，你应该能独立解决”相邻约束怎么排""方程整数解有多少个""多个集合的并有多大”这类标准问题，并知道什么时候会因为混淆有序与无序而算错。
1. 加法原理与乘法原理
加法原理：完成一件事有 类互斥的办法，第 类有 种做法，则总数为
“互斥”是关键：每类办法之间不重叠，才能直接相加。
乘法原理：完成一件事分 个依次进行的步骤，第 步有 种做法，则总数为
两步的选择相互独立、可以配对，才有乘积。一个常见的检查口径：先问自己”这些选择能不能任意搭配”，能——乘，不能——分类后用加。
例：从北京到上海有 4 班高铁、2 班飞机，从上海到杭州有 3 班动车。全程（北京→上海→杭州）的方案数是乘法：，或者先算京沪有 种（加法），再乘 。注意第一步内部用加法（互斥），两步之间用乘法（独立），实际计数几乎总是两种原理的嵌套。
2. 排列与组合：核心公式的推导
从 个不同元素中取 个（），问”有多少种取法”，答案取决于两件事：是否放回、取出的 个是否讲顺序。
2.1 排列数 ：有序、不放回
把取 个元素看成 个依次进行的步骤：第 1 个位置有 种选择，第 2 个位置剩 种，……，第 个位置剩 种。由乘法原理，排列数（取出后讲顺序）为
其中 是 的阶乘，并规定 。当 时就是全排列 。
2.2 组合数 ：无序、不放回
若取出的 个元素不讲顺序，直接数排列会重复：同一组 个元素有 种不同的排列次序，它们在这 个排列里被各数了一次。所以要除以 消除重复：
这个数读作”从 个中选 个”，称为二项式系数。由公式立得对称性 ——“选 个留下”与”选 个扔掉”是一回事。
2.3 例题：相邻约束用捆绑法
例 1 8 个人排成一列照相，其中甲、乙两人必须相邻，有多少种排法？
解：把甲、乙捆成一个整体，与其余 6 人共 7 个”物体”全排列，有 种；捆在一起的甲乙内部有 种次序。由乘法原理，总数为
思路小结：“必须相邻”→ 捆绑；“不得相邻”→ 先排其余元素、再插空。约束计数的通用策略是先处理受限对象，再让自由对象填空。
2.4 可重复、讲顺序的情形
若每次取后放回、取 次且讲顺序（如长度为 的口令），每步都有 种选择，由乘法原理得 。这是最简单也是最容易被低估的情形——计数前先确认”是否放回”。
3. 二项式定理、帕斯卡恒等式与杨辉三角
3.1 二项式定理
二项式定理：对任意数 与正整数 ，
用组合意义证明：把 写成 个因子 的乘积。展开时，从每个因子中选出 或 之一相乘，得到形如 的项。 出现多少次，就等于”从 个因子里挑出哪 个贡献 “的选法数，即 。对 求和即得定理。
这个证明值得记住：它展示了组合证明的标准手法——两边数同一个集合，说明它们相等。令 得到常用推论
令 得到交错和 （），即偶数大小子集与奇数大小子集一样多。
3.2 帕斯卡恒等式与杨辉三角
帕斯卡恒等式：对 ，
证明（分类计数）：从 个元素中选 个，固定某个元素 ，所有选法分两类——含 的：再从其余 个中选 个，共 种；不含 的：从其余 个中选 个，共 种。两类互斥且穷尽，相加即得。
把 按 成行、 成列排列，每个数等于肩上两数之和，这就是杨辉三角（西方称 Pascal 三角）：
第 行恰好是 的系数，因为帕斯卡恒等式正是”系数由上一行递推生成”的规则。
4. 容斥原理
直接算 时， 被算了两遍，要减回去：
三个集合时，减两两交集会把三者交集多减一次，要再加回来：
一般形式：对任意有限个集合 ，
规律是”奇数个集合的交相加，偶数个的交相减”。它也可以写成补集形式：
即”全集中不满足任何一条性质的元素个数”。
例题：容斥求并集与”不被整除”的数
例 2 在 到 的正整数中，（a）能被 、 或 整除的数有多少个？（b）不能被 、、 中任何一个整除的数有多少个？
解：记 为 到 中能被 整除的数集。用 表示不超过 的最大整数（取整），则 ；两个数的公倍数构成其最小公倍数的倍数， 两两互素，故 。先算各层交集：
(a) 由容斥原理，
(b) 用补集形式，。
思路小结：“能被至少一个整除”用并集形式（奇加偶减），“一个都不能”用补集形式。遇到”至少""至多""都不”要先把 verbal 描述翻译成集合运算，这是容斥题的一半工作量。
错排：容斥的一个漂亮应用
个元素全排列中，每个元素都不在原来位置上的排列叫错位排列，其个数记 ，结论为
且当 较大时 ，即随机排列全部错位（如所有信都装错信封）的概率趋近于 。这个公式本身由容斥原理对”第 个元素在原位”这 个性质展开得到，推导细节此处从略，记住结论即可。
例 3 4 封信随机装入 4 个写有地址的信封，求全部装错的方案数。
解：这就是 。由容斥：设 为”第 封信装对”的排列集，；；；四重交为 。全部装错即四个性质都不成立的排列数：
与公式 一致。
5. 鸽巢原理
基本形式：把 个物体放进 个盒子，至少有一个盒子里装了不少于两个物体。
证明只需一句反证：若每个盒子至多一个，总数至多 ，矛盾。
加强形式（一句话）：把 个物体放进 个盒子，至少有一个盒子装了不少于 个物体，其中 表示上取整。反证同基本形式：若每盒至多 个，总数至多 。
这个原理看似平凡，威力在于自己构造”盒子”——通常是把对象按某个不变量（余数、奇偶、区间）分类。
例题：同余类当盒子
例 4 任意给定 个整数，其中必有两个数之差能被 整除。
证明：按模 的余数把所有整数分类。模 的余数只有 共 种，把它们当作 个盒子， 个数放进 个盒子，由鸽巢原理必有两数同余数，设其为 。同余保持减法，故 ，即这两数之差被 整除。
思路小结：题目出现”必有""必存在”且涉及差、余数、整除时，优先考虑按模某个数的余数分类。这类题的难点不在原理，而在选对分类标准。
6. 可重复选取：隔板法
问题：把 个相同的元素放进 个不同的盒子（允许空盒），有多少种方法？等价地，方程
有多少组解？也等价于：从 种物品中可重复地选 件，有多少种选法（只关心每种选几件，不关心先后）。
推导（隔板法）：把 个相同元素排成一行，用 块相同的隔板插入队列来分界——第 1 块板左边是盒子 1 的元素，两块板之间是盒子 2 的，……，第 块板右边是盒子 的。元素相同、隔板也相同，一种放法唯一对应”元素与隔板的一个排列”。一行共有 个位置，从中选出哪 个放元素（其余放隔板）即可，所以方案数为
这也解释了为什么它和 只差在”是否可重复”：可重复选取相当于给每个盒子预先存入”一个免费元素”的许可。若要求每个盒子至少一个（即 ），先给每个盒子各放 1 个，剩下的 个任意分，方案数为 。
例题：方程整数解的个数
例 5 求方程 满足 的整数解的个数。
解：先”预支”下界：令 ，，方程化为
这相当于把 个相同元素放进 个不同盒子，由隔板法，解的个数为
思路小结：隔板法题的三步——化为”相同元素进不同盒子”的形式，用代换 消去正下界，套 。判断标准就一条：元素是否相同、盒子是否不同。
7. 常见错误
有序与无序混淆。从 个中选 个，“选出来”用组合数 ，“选出来再排队”用排列数 ，相差一个 。判断口径：交换两个元素的位置，结果算不算新方案？算——有序，用排列；不算——无序，用组合。
重复计数后忘了除以 。典型场景是分组问题：把 个人分成 3 个无编号的小组、每组 2 人。按”依次选出三组”算是 ，但这样每组被编了号（第一组、第二组、第三组），而 3 个组之间本无次序，同一分法被算了 遍，正确答案要除以 ：
一般地，把 个人均分成 个无编号小组（每组 人）的方案数是 。记住除的是”被你无意中编了号的那 个对象的排列数”——关键是想清楚自己数的对象到底带不带顺序。
容斥符号写反。原则是 的符号为 ：单个集合加，两两交减，三重交加，依此交错。写完后可用一个小的退化情形自检（如所有交集为空时并集应等于各集之和）。
隔板法用于不同元素。隔板法的前提是元素相同；若元素不同（如 5 个不同的奖项分给 3 个人），则属于可重复分配的另一类问题，要对每个元素独立选择归属，用乘法原理或生成函数，不能直接套 。
8. 练习
练习 1 5 本不同的书排放在书架上，其中《离散数学》与《图论》必须相邻，《概率论》不能排在两端。共有多少种排法？
答案：先捆绑前两本为一个整体（内部 种），再与剩下 2 本共 4 个物体排列。《概率论》不在两端：先排其余 3 个物体有 种，产生 4 个空档，其中两端 2 个不能用，有 2 个可选空档插入《概率论》。总数 。
练习 2 求 的非负整数解中满足 的解的个数。
答案：令 ，化为 的非负整数解，隔板法得 。
练习 3 在 到 中，能被 或 整除的整数有多少个？
答案：，，（ 的最小公倍数为 ）。容斥：。
练习 4 任意取 6 个整数，证明其中必有两个数之差能被 整除。
答案（提示）：按模 的余数分类，共 个余数类；6 个数放入 5 类，必有两数同余；同余保持减法，其差被 整除。
练习 5 利用二项式定理计算 ，并解释其组合意义。
答案：令 ，得 。组合意义： 元集合的所有子集个数——每个元素”选或不选”独立，共 种，按子集大小分类即二项式系数之和。