培玉 · 一试

专题地图 › 排列组合与概率

排列组合

从这里开始

目标训练建设中。知识要点、方法卡和分级真题已可使用；先从一道真题开始，卡住时逐级看提示，核对后再换题验证。

从 F1 第一题开始随机来一道 F2

本专题核心公式速查

排列组合题先问“两个方案何时算相同”，再决定怎样分解。子集可以逐元素编码，排列的邻接条件可以留下骨架后插空，整数条件则常由一个规范参数统领。遇到更深的置换限制，要证明拆分后的对象仍属于同一类，并检查每个方案能否唯一恢复。

1. 先修与破题直觉：先在纸上列清“对象是否区分、位置是否有序、是否可重复”；同一组成员排不排列，答案可能相差一个阶乘。

2. 核心条件辨析：用乘法原理时每步选择须符合之前的结果；除以重复次数时每个对象须被表示同样多次；首位非零与内部不相邻都是附加条件。

3. 典型误区对比：用下方前导零与插空卡检查模型，再做概念自测；把数字串和四位数分开，把相同的字母和有标签的字母分开。

4. 方法迁移带练：三个相同 $A$ 与一个 $B$ 不限首尾有四种；若只允许 $B$ 放在内部，则为两种。明确空隙是否包含首尾后再套组合数。

5. 分级真题实战：先练“标号与等价关系校正重数”及“删除特殊元素后按空隙插入”，再挑战“中间位分类与余数状态”；数完后选一个小规模手列检查一一对应。

先修（培玉高中数学）：分类加法计数原理与分步乘法计数原理排列与组合二项式定理集合的基本运算

知识要点

先确定数的是集合还是序列

选出的成员相同是否就算同一个对象，要在套公式前决定。 $0 \leq r \leq m$ 时，从 $m$ 个不同对象取 $r$ 个的组合数为 $(r m)$ ；若还要安排顺序，则为 $m! / (m - r)!$ 。例：从五人选两人组成小组有 $10$ 种，分别担任两个不同职务有 $20$ 种。把公差为正的数列倒序，会得到另一条数列，却不会得到新的元素集合。

互斥分类相加，连续选择相乘

分类必须覆盖全部对象且彼此不重叠；分步时每一步的可选数须在此前选择给定后成立。例：一人从三门课中至少选一门，有 $2^{3} - 1 = 7$ 种；两位有姓名的学生各自独立选课有 $7^{2} = 49$ 种。若题目另规定两人不能选同一门，就不能沿用独立相乘。分组或分配题也要区分对象可辨与容器可辨。

至少出现一类先看补集

长度 $m \geq 1$ 的词使用 $q \geq 2$ 个字符且相邻不同，共 $q (q - 1)^{m - 1}$ 个。要求各类别都出现时，可对“缺少某类”容斥，每个交集仍须保留邻接限制。例：三类各两个字符，三位词三类全出现且相邻不同，有 $6 \cdot 5^{2} - 3 \cdot 4 \cdot 3^{2} + 3 \cdot 2 = 48$ 个；也可先排三类别，再各选字符，得到 $3! \cdot 2^{3} = 48$ 。

按元素记录归属，也可以记录权重

一个元素相对有序集合对 $(A, B)$ 有四种状态：都不属、仅属 $A$ 、仅属 $B$ 、同时属于。例：四元全集中，交集大小为一、并集大小为三的有序对有 $(3 4) (1 3) 2^{2} = 48$ 个。若每个元素选入时贡献权 $t_{i}$ ，全部子集权和为 $\prod_{i} (1 + t_{i})$ ；空集贡献为 $1$ ，带负权时可以找切换元素的抵消配对。

相同元素、组名和圆周各有不同重数

含 $m$ 个元素、各类重复次数为 $r_{1}, \dots, r_{s}$ 的多重集，线性排列数是 $m! / \prod r_{i}!$ 。例： $0, 0, 1, 2$ 的线性词有 $12$ 个，其中首位为零有 $6$ 个，故四位数只有 $6$ 个。不同元素的圆排列只把旋转视为相同，四元素有 $3! = 6$ 种；无标号分组则须另查交换组名造成几次重复，不能一律除某个阶乘。

插空要保留邻接与唯一复原

先安排骨架，再选允许的间隙；删去插入元素后应能唯一恢复原方案。例：三个相同的 $A$ 形成四个含首尾的空隙，把两个相同的 $B$ 放入不同空隙，可得 $(2 4) = 6$ 个无相邻 $B$ 的词。若某空隙已经放入必须紧贴两端的特殊卡，就不能再塞其他元素破坏邻接。圆周空隙数与线性排列含首尾的空隙数也不同。

用唯一参数把无序选择规范化

等差、等比及整数区间计数，先证明每个对象唯一对应所用参数。例：从一到十二取三个不同数构成等差数列，先按递增写为 $s, s + d, s + 2 d$ ，有 $d = 1, \dots, 5$ ，共 $10 + 8 + 6 + 4 + 2 = 30$ 个元素集合；若数列方向也计入，则有 $60$ 条。整除公比须为整数时，首项范围常由取整函数给出，不能先连续估计再舍入总数。

局部限制需要保留足够状态

相邻两位的条件可固定中间位或保留最后一位；连续三位的条件通常要保留最后两位，或先降到余数状态。例：只用 $0, 1, 2$ 组成三位数，首位非零、相邻差至多一，按十位为 $0, 1, 2$ 分类分别有 $2, 6, 4$ 种，总计 $12$ 。余数序列数完后，还要检查同余类中不同实际数字能否自由交换。

方法卡

“至少一个”“都要有”的计数题：先数不合格的，再减去

正面要分很多情况时，先数全部，再减去不合格的。2 类不合格情况有重叠时，重叠部分被减了 2 次，要加回来 1 次；3 类及以上用进阶里的公式。

完整讲解 · 例题 · 可练 21 题

一、是什么

补集：合格 = 全部 − 不合格

每个对象要么合格，要么不合格，所以合格数 = 全部 − 不合格数。例如 ${1, 2, 3}$ 的子集中至少含 1 个奇数的有几个？每个元素有选、不选 2 种可能，子集共 $2 \times 2 \times 2 = 8$ 个。不含奇数的子集只能从 ${2}$ 里选，有 $2$ 个。所以答案是 $8 - 2 = 6$ 。不合格的情况只有极少几种时，这个办法最省事：4 道判断题的答卷，不能全答“对”也不能全答“错”，共 $2^{4} - 2 = 14$ 种。

组合数：从一堆里选几个

$(k n)$ 表示从 $n$ 个不同的东西里选 $k$ 个、不管先后的选法数。例如 $(3 10) = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120$ ：按先后顺序选有 $10 \times 9 \times 8$ 种，而同一组 3 个数被排了 $3 \times 2 \times 1$ 次，所以要除掉。

重叠要加回来

两类不合格情况 $P, Q$ 合起来的个数是 $∣ P ∣ + ∣ Q ∣ - ∣ P \cap Q ∣$ ，这里 $∣ P ∣$ 表示 $P$ 里的个数， $P \cap Q$ 表示同时属于 $P$ 和 $Q$ 的部分。同时属于两类的对象在 $∣ P ∣ + ∣ Q ∣$ 里数了 2 次，所以减掉 1 次。例如 1 到 10 中被 2 或 3 整除的数：被 2 整除的 5 个，被 3 整除的 3 个，被 6 整除的 1 个（就是 6），共 $5 + 3 - 1 = 7$ 个。

先看一道例题

例 1：乘积是偶数

从 $1, 2, \dots, 10$ 中选 3 个不同的数，要求乘积是偶数。有多少种选法？

怎么看出来：

乘积是偶数等于“至少有 1 个偶数”，正面要分 1、2、3 个偶数，反面只有“全是奇数”1 种情况。

解：

全部选法有 $(3 10) = 120$ 种。乘积是奇数时 3 个数都是奇数，只能从 $1, 3, 5, 7, 9$ 中选，有 $(3 5) = \frac{5 \times 4 \times 3}{3 \times 2 \times 1} = 10$ 种。所以有 $120 - 10 = 110$ 种。检查：按偶数个数正面数， $(1 5) (2 5) + (2 5) (1 5) + (3 5) = 50 + 50 + 10 = 110$ ，一致。

答案：

$110$ 种。

二、什么时候想到它

题目里看到	应该想到
至少含 1 个、乘积是偶数（至少 1 个偶数）	不合格是“1 个也没有”，常常只有 1 种情况，先算它
既含某一类，又含另一类	不合格有 2 类，注意它们的重叠
只禁止全部相同、全部落在同一处	不合格的情况只有几种，全部减去它们
每类、每个盒子都要有	对“缺某一类”容斥（见进阶“各类都要有”的容斥）
不能相邻、不能连续出现某串	把相邻的捆起来数，再减去（见进阶“排列里的相邻限制”）
相邻不同，同时要求某些字符出现	用缩小后的字符集重算 $q (q - 1)^{m - 1}$ （见进阶“带相邻限制的容斥”）

三、怎么用

写清全部对象并数出来。例如用 $a, b, c$ 写长度为 3 的串，要求 $a, b$ 都出现。全部有 $3^{3} = 27$ 个。
写清不合格的是什么。这里是 $P$ ：不含 $a$ ； $Q$ ：不含 $b$ 。只要有一个发生就不合格。
分别数每一类，字符要跟着减少。不含 $a$ 的串只用 $b, c$ ，有 $2^{3} = 8$ 个；不含 $b$ 的串也有 8 个。
数重叠部分。既不含 $a$ 又不含 $b$ 的串只用 $c$ ，有 1 个。不合格的共有 $8 + 8 - 1 = 15$ 个。
用全部减去不合格的，再检查。 $27 - 15 = 12$ 。直接数：含 $a, b, c$ 各 1 个的有 6 个， $a, a, b$ 型有 3 个， $a, b, b$ 型有 3 个，也是 12 个。

四、再做一道

例 2：同时含两类数

${1, 2, \dots, 12}$ 有多少个子集，既含 3 的倍数，又含 4 的倍数？

怎么看出来：

“既含……又含……”不合格的有 2 类：不含 3 的倍数、不含 4 的倍数。12 同时是 3 和 4 的倍数，所以要小心重叠。

解：

全部子集有 $2^{12} = 4096$ 个。3 的倍数是 $3, 6, 9, 12$ ，共 4 个，不含它们的子集从其余 8 个数里选，有 $2^{8} = 256$ 个。4 的倍数是 $4, 8, 12$ ，共 3 个，不含它们的子集有 $2^{9} = 512$ 个。两者都不含时，要避开 $3, 4, 6, 8, 9, 12$ 共 6 个数，有 $2^{6} = 64$ 个。不合格的共有 $256 + 512 - 64 = 704$ 个，所以答案是 $4096 - 704 = 3392$ 个。

答案：

$3392$ 个。

五、容易错在哪

相减时要用同一种数法。全部按有序数，不合格的也要按有序数。
2 类不合格情况有重叠时不能直接相加，要加回重叠部分；3 类及以上按进阶里的公式逐层加减。
缺一类时字符集变小了， $q (q - 1)^{m - 1}$ 里的 $q$ 也要变小。
“缺指定的一类”和“恰好缺一类”不同，前者还包含同时缺其他类的情况。
先检查题目是否允许空集。“非空子集”要再减去空集，而“至少含 1 个”已经排除了空集，不要多减。

进阶：“各类都要有”的容斥

3 类不合格：减单类，加两两，再减 3 类都有的

$∣ P \cup Q \cup R ∣ = ∣ P ∣ + ∣ Q ∣ + ∣ R ∣ - ∣ P \cap Q ∣ - ∣ P \cap R ∣ - ∣ Q \cap R ∣ + ∣ P \cap Q \cap R ∣$ ，其中 $\cup$ 表示至少属于其中一类。为什么对？同时属于 3 类的对象，前 3 项数了 3 次，中间 3 项减了 3 次，最后一项再加 1 次，正好算 1 次；只属于 2 类的对象是 $2 - 1 = 1$ 次。例如 ${1, 2, 3, 4, 5, 6}$ 的子集要同时含 ${1, 2}$ 中的数、 ${3, 4}$ 中的数、 ${5, 6}$ 中的数：全部 $2^{6} = 64$ 个；缺某一组时只从其余 4 个数里选，有 $2^{4} = 16$ 个；缺某 2 组时有 $2^{2} = 4$ 个；3 组都缺时有 1 个。答案是 $64 - 3 \times 16 + 3 \times 4 - 1 = 27$ 。检查：每组有 3 种非空选法， $3^{3} = 27$ 。“每个对象选一类，每类都要出现”的题也这样算，缺一类就是可选的类变少。

已经有保证的类不用扣

如果某一类已经有对象了，就不用再扣“缺这一类”。例如 5 张不同的卡放进甲、乙、丙，每封不空，其中 X 指定放甲，Y 指定放乙。甲、乙已经不空，只需保证丙不空：其余 3 张有 $3^{3} = 27$ 种放法，丙为空时每张只有 2 种，有 $2^{3} = 8$ 种，答案是 $27 - 8 = 19$ 。题目看起来是抽取、涂色，只要能写成“每个对象选一类”，都可以先看哪些类已有保证。

“恰好缺一类”和“缺指定的一类”不同

用 $a, b, c, d$ 写长度为 3 的串，第 1 位必须是 $a$ 。缺指定字母 $b$ 的串，后 2 位从 $a, c, d$ 里选，有 $3^{2} = 9$ 个，这里面还有 $a cc$ 、 $aaa$ 这样同时缺别的字母的串。恰好缺 1 个字母时，先选缺 $b, c, d$ 中的哪个（3 种），其余 2 个字母要占满后 2 位（2 种），共 $3 \times 2 = 6$ 个。检查：恰缺 1 个有 6 个，恰缺 2 个有 $3 \times (2^{2} - 1) = 9$ 个，恰缺 3 个只有 $aaa$ ，合计 $6 + 9 + 1 = 16 = 4^{2}$ 。

例 3：只要求其中几个字母出现

用 $a, b, c, d$ 写长度为 5 的串，字母可重复。要求 $a, b, c$ 都至少出现 1 次， $d$ 可出现可不出现。有多少个串？

怎么看出来：

要求出现的只有 3 个字母，所以只对 $a, b, c$ 容斥， $d$ 不用扣。

解：

全部有 $4^{5} = 1024$ 个。不含某个指定字母（ $a, b, c$ 之一）时只剩 3 个字母，有 $3^{5} = 243$ 个，共 3 类。同时不含其中 2 个时只剩 2 个字母，有 $2^{5} = 32$ 个，共 3 种。 $a, b, c$ 都不含时只有 $ddddd$ ，有 1 个。按 3 类的公式，不合格的有 $3 \times 243 - 3 \times 32 + 1 = 634$ 个。答案是 $1024 - 634 = 390$ 个。

答案：

$390$ 个。

进阶：带相邻限制的容斥

相邻不同：字符集变了，公式跟着变

用 $q$ 个字符写长度为 $m$ 的串，相邻 2 位不能相同：第 1 位有 $q$ 种，之后每一位只要避开前一位，各有 $q - 1$ 种，共 $q (q - 1)^{m - 1}$ 种。扣掉“不含某字符”的串时，要把 $q$ 换成缩小后的字符数再算，不能写成 $q^{m}$ 。例如 $q = 3, m = 3$ 时有 $3 \times 2^{2} = 12$ 个，不含某个字符时 $q = 2$ ，有 $2 \times 1^{2} = 2$ 个。

例 4：相邻不同且含指定字符

用 $1, 2, 3, 4$ 写长度为 5 的串，相邻 2 位不能相同，并且 1 和 2 都要出现。有多少个串？

怎么看出来：

“都要出现”用容斥，“相邻不同”决定每一步用 $q (q - 1)^{m - 1}$ ，并且 $q$ 随字符集变化。

解：

全部有 $4 \times 3^{4} = 324$ 个。不含 1 时只用 3 个字符，有 $3 \times 2^{4} = 48$ 个；不含 2 时也有 48 个。1、2 都不含时只用 $3, 4$ ，相邻不同的串只有 $34343$ 和 $43434$ ，有 $2 \times 1^{4} = 2$ 个。不合格的有 $48 + 48 - 2 = 94$ 个，答案是 $324 - 94 = 230$ 个。

答案：

$230$ 个。

进阶：排列里的相邻限制

必须相邻的情况：捆起来数

$n!$ 表示 $n \times (n - 1) \times \dots \times 1$ ，是 $n$ 个不同对象排成一行的方法数。甲、乙相邻时，把两人当成 1 个人。例如甲、乙、丙、丁排队，丙站首位，甲、乙不相邻：丙固定后其余 3 人有 $3! = 6$ 种；甲、乙相邻时，甲乙块和丁排 $2! = 2$ 种，内部 2 种，共 4 种。答案是 $6 - 4 = 2$ ，就是甲丁乙和乙丁甲（都排在丙后面）。要求连续出现固定的字符串时，把它粘成 1 块，内部不再排。例如 $a, b, c, d$ 排成串，不能出现 $ab$ ，且 $c$ 不在首位：含 $ab$ 的有 $3! = 6$ 个， $c$ 在首位的有 $3! = 6$ 个，两者同时发生时 $c$ 在首位， $ab$ 块和 $d$ 排 $2! = 2$ 个。答案是 $24 - 6 - 6 + 2 = 14$ 。

选数不能相邻：先压紧，再选

从 $1, \dots, 7$ 中选 3 个数，必须含 1，并且至少有 2 个数相邻，有几种？含 1 的选法是 $(2 6) = 15$ 种。再数 3 个数两两不相邻的：另 2 个数 $b < c$ 只能在 $3, \dots, 7$ 中，且 $c \geq b + 2$ 。令 $c^{'} = c - 1$ ，则 $b < c^{'}$ ，它们是 $3, \dots, 6$ 中不同的 2 个数；反过来，任选这样 2 个数，把大的加 1，也满足要求。所以有 $(2 4) = 6$ 种。答案是 $15 - 6 = 9$ 。

例 5：位置限制和相邻限制一起

甲、乙、丙、丁、戊、己 6 人排成一行。甲不站首位，乙不站末位，丙、丁不相邻。有多少种排法？

怎么看出来：

有 3 个“不能”，正面分类很多，所以设 3 类不合格情况来容斥。设 $P$ ：甲在首位； $Q$ ：乙在末位； $R$ ：丙、丁相邻。

解：

全部 $6! = 720$ 种。 $∣ P ∣ = 5! = 120$ ， $∣ Q ∣ = 120$ 。 $R$ ：丙、丁捆成 1 个，5 个单位排 $5!$ 种，内部 2 种， $∣ R ∣ = 240$ 。 $∣ P \cap Q ∣ = 4! = 24$ 。 $P \cap R$ ：甲固定在首位，其余 4 个单位（丙丁块和另 3 人）排 $4!$ 种，内部 2 种，共 48 种； $Q \cap R$ 也是 48 种。 $P \cap Q \cap R$ ：甲、乙固定，中间 3 个单位排 $3!$ 种，内部 2 种，共 12 种。不合格的有 $120 + 120 + 240 - 24 - 48 - 48 + 12 = 372$ 种。答案是 $720 - 372 = 348$ 种。

答案：

$348$ 种。

进阶：不分编号的分组

不分编号的 2 组：先编号，再看要不要除以 2

2 组没有编号时，先临时叫甲组、乙组，每种分法被“交换甲乙”数了 2 次，所以最后除以 2。如果有办法认出每一组，就不用除。例如 6 个人分成没有编号的 2 组，每组至少 2 人，甲、乙必须同组：含甲的那组可以认出来，所以不重复。其余 4 人各选进这一组或另一组，有 $2^{4} = 16$ 种。另一组至少 2 人，要去掉它有 0 人（1 种）和 1 人（4 种）的情况，答案是 $16 - 1 - 4 = 11$ 。

真题

按这个方法练 · 21 题

收起并返回方法目录

子集、集合对的计数：给每个元素列状态，再相乘

不要整体去想集合长什么样，而是逐个元素问：它可以处在哪几种状态？元素之间互不影响时，把各自的状态数乘起来。有总数限制时，先选哪些元素用哪种状态。

完整讲解 · 例题 · 可练 18 题

一、是什么

每个元素问一次：选还是不选

确定一个子集，就是对每个元素回答“选”或“不选”，不同的回答给出不同的子集。所以 $n$ 个元素的集合有 $2^{n}$ 个子集，空集是“全不选”。有规定的元素只剩 1 种状态： ${1, 2, 3, 4}$ 的子集中含 1、不含 2 的有 $1 \times 1 \times 2 \times 2 = 4$ 个，它们是 ${1}, {1, 3}, {1, 4}, {1, 3, 4}$ 。

2 个集合一起看：列出归属状态

$A \cup B$ 表示至少在 $A, B$ 之一中的元素， $A \cap B$ 表示同时在两者中的元素。对有序的 $(A, B)$ ，每个元素有 4 种状态：只在 $A$ 、只在 $B$ 、都在、都不在。条件就是去掉某些状态。例如 $A \subseteq B$ （ $A$ 的元素都在 $B$ 里）去掉“只在 $A$ ”，每个元素剩 3 种。所以 ${1, 2}$ 上有 $3^{2} = 9$ 对。检查： $B$ 为空时 $A$ 有 1 种， $B$ 为 ${1}$ 或 ${2}$ 时 $A$ 各有 2 种， $B = {1, 2}$ 时 $A$ 有 4 种， $1 + 2 + 2 + 4 = 9$ 。

有总数限制：先选位置，再选状态

“恰好 2 个元素处于某状态”把元素牵连在一起，不能直接把每个元素的状态数相乘。要先用组合数选出这 2 个元素， $(k n)$ 表示从 $n$ 个里选 $k$ 个的选法数，例如 $(2 6) = \frac{6 \times 5}{2 \times 1} = 15$ 。选好以后，其余元素再各自选状态。

先看一道例题

例 1：包含关系和固定元素

${1, 2, \dots, 7}$ 上的有序集合对 $(A, B)$ 满足 $A \subseteq B$ ，且 $1 \in A$ ， $2 \in / B$ 。有多少对？

怎么看出来：

条件都是对单个元素说的，元素之间互不影响，所以每个元素列状态。

解：

$A \subseteq B$ 时每个元素有 3 种状态：都不在、只在 $B$ 、都在。元素 1 要在 $A$ 中，又因为 $A \subseteq B$ ，所以只能“都在”，1 种。元素 2 不在 $B$ 中，也就不在 $A$ 中，只能“都不在”，1 种。其余 $3, 4, 5, 6, 7$ 共 5 个元素各 3 种。总数是 $1 \times 1 \times 3^{5} = 243$ 。

答案：

$243$ 对。

二、什么时候想到它

题目里看到	应该想到
求子集个数、子集对的个数	每个元素列状态，再相乘
含 $\subseteq$ 、 $\cup$ 、 $\cap$ 的固定条件	列出归属状态，去掉不允许的
某元素必须选、不能选	它只剩 1 种状态，其余元素自由
交集恰有几个、某状态恰有几个	先选这几个元素，再给其余元素选状态
几个人各选、每人至少选 1 个	算每人的选法，再相乘（见进阶“多人选择”）
求所有子集的积之和	写成 $\prod (1 + t_{i})$ （见进阶“带权的子集”）
权值带 $\pm$ 号	切换一个元素配对（见进阶“切换配对”）

三、怎么用

确定“元素”是谁，以及对象是否有序。例如 $U = {1, 2, 3}$ ，求有序对 $(A, B)$ ，满足 $A \cup B = U$ 且 $1 \in A \cap B$ 。
列出每个元素的全部状态：只在 $A$ 、只在 $B$ 、都在、都不在。
用条件筛状态。 $A \cup B = U$ 去掉“都不在”，剩 3 种。元素 1 必须在两个集合里，只剩“都在”1 种。
没有总数限制时，把各元素的状态数相乘： $1 \times 3 \times 3 = 9$ 。有“恰好几个”时，先选元素再相乘。
检查有序和边界。 $A \neq = B$ 时， $(A, B)$ 和 $(B, A)$ 算不同的对，不除以 2。这 9 对都含元素 1，枚举 $U$ 的所有集合对也恰好得到 9 对。

四、再做一道

例 2：恰好几个元素处于某状态

$U = {1, 2, 3, 4, 5, 6}$ ，有序对 $(A, B)$ 满足 $A \subseteq B \subseteq U$ ，且恰有 2 个元素在 $B$ 中但不在 $A$ 中。有多少对？

怎么看出来：

“恰有 2 个”是总数限制，不能直接写 $3^{6}$ 。先选这 2 个元素。

解：

元素有 3 种状态：都不在、只在 $B$ 、都在。先从 6 个元素里选 2 个处于“只在 $B$ ”，有 $(2 6) = 15$ 种。其余 4 个元素不能再是“只在 $B$ ”，只能选“都不在”或“都在”，各 2 种，有 $2^{4} = 16$ 种。总数是 $15 \times 16 = 240$ 。

答案：

$240$ 对。

五、容易错在哪

有序集合对 $(A, B)$ 和 $(B, A)$ 通常算不同的对，不要除以 2。只有题目说不分先后时才除，并且要处理两者相同的情况。
数状态时不要漏掉“都不选”或“都不在”。
有“恰好几个”这样的总数限制时，不能把每个元素的状态数直接相乘，要先选元素。
只有各元素或各人的选择互不影响时才能相乘。
切换配对之前先确认每个子集恰好在一对里，并确认切换后权值确实变号。

进阶：3 个集合的状态

3 个集合：状态最多 8 种

对 $(A, B, C)$ ，每个元素在每个集合里是在或不在，共 $2^{3} = 8$ 种状态。条件逐个去掉状态： $A \cup B \cup C$ 是全集（ $\cup$ 表示至少在其中一个）去掉“都不在”； $A \cap B \cap C$ 为空（ $\cap$ 表示同时在）去掉“都在”。不同元素的条件可以不同，这时分别数再相乘。链 $A \subseteq B \subseteq C$ 只看元素最早进入哪一层：进 $A$ 、进 $B$ 、进 $C$ 、都不进，共 4 种状态。

例 3：3 个集合的归属

有序 3 元组 $(A, B, C)$ 是 ${1, 2, 3, 4, 5}$ 的子集，满足 $A \cup B \cup C = {1, 2, 3, 4, 5}$ ，且 $A \cap B \cap C = \emptyset$ 。有多少组？

怎么看出来：

并集和交集的条件都可以逐个元素检查，没有总数限制。

解：

每个元素原有 $2^{3} = 8$ 种状态。并集是全集，去掉“都不在”；3 个集合的交集为空，去掉“都在”。每个元素剩 6 种，且互不影响。总数是 $6^{5} = 7776$ 。

答案：

$7776$ 组。

进阶：多人选择

多人选择：互不影响才能相乘

每人的选择互不影响时，把每人的选法数相乘。甲从 3 门课里选至少 1 门，有 $2^{3} - 1 = 7$ 种；乙从另外 4 门课里至多选 1 门，有 $4 + 1 = 5$ 种；共 $7 \times 5 = 35$ 种。有“恰好”时要先定共同部分：从 5 门课中，甲选 2 门、乙选 3 门，恰有 1 门相同。共同课 5 种，甲的另一门 4 种，乙的另 2 门从余下 3 门里选， $(2 3) = 3$ 种，共 $5 \times 4 \times 3 = 60$ 种。

先有序再去序

临时给 2 组编号，每个元素有进第 1 组、进第 2 组、不选 3 种状态，人数有限制时先选元素。例如 5 张卡选出 2 组，不重叠，每组至少 2 张。按（第 1 组，第 2 组）的张数分： $(2, 2)$ 有 $(2 5) (2 3) = 30$ 种， $(2, 3)$ 有 $(2 5) = 10$ 种， $(3, 2)$ 有 10 种，共 50 种。如果 2 组不分先后，2 组非空又不重叠，交换后一定是另一种编号，每种分法恰好被数 2 次，所以是 $50 \div 2 = 25$ 种。题目没说不分先后时不要除以 2。

例 4：独立选择之后再扣

甲、乙、丙 3 人选 5 门不同的课。要求每门课恰有 2 人选，且每人至少选 1 门。有多少种方案？

怎么看出来：

这里每门课才是“元素”：每门课选哪 2 个人，互不影响。“每人至少 1 门”用补集。

解：

每门课从 3 人中选 2 人，有 $(2 3) = 3$ 种，5 门课共 $3^{5} = 243$ 种。不合格的是有人 1 门没选。若甲没选，每门课都只能是乙、丙，只有 1 种；乙、丙同样各 1 种。不可能有 2 人都没选，因为每门课要 2 个人。所以不合格的有 3 种，答案是 $243 - 3 = 240$ 种。

答案：

$240$ 种。

进阶：带权的子集

带权的子集：展开乘积

$(1 + x) (1 + y) = 1 + x + y + x y$ ，展开式的 4 项正好对应 ${x, y}$ 的 4 个子集：每个括号选 1 表示不选这个元素，选字母表示选它。所以“所有子集的元素积之和”等于 $\prod_{i} (1 + t_{i})$ ，其中 $\prod$ 表示把后面各项全部相乘，空集的积规定为 1。例如 ${2, 3}$ ： $1 + 2 + 3 + 6 = 12 = (1 + 2) (1 + 3)$ 。只要非空子集，就再减去 1。

例 5：乘积求总和

对 ${1, 2, \dots, n}$ 的每个非空子集，计算其中所有元素倒数的积。把这些积全部相加，结果是多少？

怎么看出来：

所有子集的积之和可以写成乘积。每个元素贡献 1（不选）或 $\frac{1}{j}$ （选）。

解：

所有子集（含空集，其积记为 1）的和是 $\prod_{j = 1}^{n} (1 + \frac{1}{j}) = \frac{2}{1} \times \frac{3}{2} \times \frac{4}{3} \times \dots \times \frac{n + 1}{n}$ 。相邻的分子和分母相消，结果是 $n + 1$ 。减去空集的 1，得 $n$ 。检查 $n = 2$ ： $1 + \frac{1}{2} + \frac{1}{2} = 2$ 。

答案：

$n$ 。

例 6：恰好取几个

第 $i$ 个盒子里有 $i$ 个不同的球（ $i = 1, 2, 3, 4$ ）。每个盒子至多取 1 个球，恰好取 3 个球的取法有多少种？

怎么看出来：

第 $i$ 个盒子的状态是不取或取某 1 个，用 $1 + i t$ 表示， $t$ 记录取了 1 个。

解：

$(1 + t) (1 + 2 t) (1 + 3 t) (1 + 4 t)$ 中 $t^{3}$ 的系数是任选 3 个括号取字母项的积之和： $1 \times 2 \times 3 + 1 \times 2 \times 4 + 1 \times 3 \times 4 + 2 \times 3 \times 4 = 6 + 8 + 12 + 24 = 50$ 。也可以直接看：选哪 3 个盒子，再把各盒的球数相乘，正是这 4 个积。

答案：

$50$ 种。

进阶：切换配对

切换一个元素：让正负抵消

给每个子集配对：含元素 $x$ 的和不含 $x$ 的。若这样改动恰好让权值变号，每对的和是 0，总和就是 0。例如权值取 $(- 1)^{元素个数}$ 时，切换任意元素都使元素个数变化 1，所以 ${1, 2, 3}$ 的总和是 $1 - 3 + 3 - 1 = 0$ 。切换后不一定整对抵消，要算每对的和。例如把子集从大到小交替加减，求 ${1, 2, 3, 4}$ 中所有含 1 的子集的结果之和。切换最大的 4：不含 4 的子集结果为 $s$ ，加入 4 后变成 $4 - s$ ，每对和为 4。这样的子集含 1、不含 4，由 2、3 自由决定，有 4 对，共 16。又如权值是“元素个数的平方 × 元素积”：把 $- 1$ 切换进去，个数 $k$ 、积 $p$ 变成 $k + 1$ 、 $- p$ ，每对的和是 $k^{2} p - (k + 1)^{2} p = - (2 k + 1) p$ 。 ${- 1, 3}$ 的非空子集总和是 $- 1 + 3 - 12 = - 10$ ；按配对算，不含 $- 1$ 的子集有空集（ $k = 0, p = 1$ ，得 $- 1$ ）和 ${3}$ （ $k = 1, p = 3$ ，得 $- 9$ ），也是 $- 10$ 。

进阶：特殊元素与按位计数

按特殊元素分类，或按位计贡献

$A_{n}^{k}$ 表示从 $n$ 个不同元素里有序取 $k$ 个的方法数，如 $A_{5}^{2} = 5 \times 4 = 20$ 。 $A_{n}^{k} - A_{n - 1}^{k}$ 就是含第 $n$ 个元素的取法数：全部减去不含它的。“含特殊元素”时，先定它的位置，再有序取其余的。例如 5 张卡中有星、月 2 张，有序取 2 张，恰含星、月中的 1 张：选哪 1 张 2 种，放哪个位置 2 种，另一张从其余 3 张里选 3 种，共 $2 \times 2 \times 3 = 12$ 种。求所有排列组成的数之和时，按位计算： $1, 2, 3$ 组成的 6 个 3 位数，每个数字在每一位各出现 2 次，总和是 $(1 + 2 + 3) \times 2 \times 111 = 1332$ 。首位不能是 0、末位要是奇数这类限制，要分开重算每个数字在每一位出现的次数。

真题

按这个方法练 · 18 题

收起并返回方法目录

临时标号方便数，去标号前核每次重数

计数中的重数，是同一个最终对象在构造过程里被算的次数。先给相同对象临时编号，或给无名组临时取名；只有证明每个最终对象的重数固定，才能统一除掉。

完整讲解 · 例题 · 可练 23 题

一、是什么

相同字母与无名组

$n$ 个全不同对象有 $n!$ 种排列， $n! = 1 \cdot 2 \dots n$ 。相同字母出现 $r$ 次时，临时编号的 $r!$ 种互换给出同一结果，应除以 $r!$ 。无名两组只有在交换两组不改变最终对象且没有固定情况时才可除以 $2$ 。

圆周只消旋转

$n$ 个不同对象绕圆排列，若只把旋转视作相同，可固定一个指定对象的位置，余下有 $(n - 1)!$ 种。镜像是否相同由题目规定，不能自行再除以 $2$ 。有重复对象时，各旋转轨道大小可能不同，不能直接套这个公式。

位置无序不等于物品无序

在 $N$ 个格子中放两个相同字母，先选无序格对有 $(2 N)$ 种。这里 $(r N) = N! / (r! (N - r)!)$ 是从 $N$ 个不同对象选 $r$ 个的子集数。若两物品颜色不同，选定格对后通常还要算两种分配。

先看一道例题

例 1：两个相同字母

字母 A、A、B、C 排成一行，有多少个不同结果？

怎么看出来：

先给两个 A 编号。

解：

临时不同的四个字母有 $4! = 24$ 种。每个最终字符串对应 A 的两种编号互换，所以重数恒为 $2$ ，得到 $24/2 = 12$ 。

答案：

$12$ 。

二、什么时候想到它

题目里看到	应该想到
同一对象有临时编号	除去编号互换的固定重数
组没有名字	检查交换组是否恒计两次
圆排列	先确认旋转和镜像的等价规则

三、怎么用

明确最终对象的相同标准。
用标号或组名方便构造。
证明每个对象被数固定几次。
除重并核小规模情况。

四、再做一道

例 2：无名两组

六个不同的人分成两个无名的三人组，有多少种分法？

怎么看出来：

先选名为第一组的三个人。

解：

临时第一组有 $(3 6) = 20$ 种选法，另一组由补集确定。每个无名分组被两组交换恰数两次，且两个互不相交的三人组不可能是同一个集合，所以答案 $20/2 = 10$ 。

答案：

$10$ 。

五、容易错在哪

没有证明重数固定时不能直接除以阶乘。
旋转等价不自动包含镜像等价，有名字或颜色的组也不能去掉名字。

真题

按这个方法练 · 23 题

收起并返回方法目录

元素不能相邻、要夹在中间：先拿走它，再往空隙里放

先把有限制的元素拿走，排好其余元素（这叫骨架），数出能放的空隙，再把拿走的元素放回去。要求它们互不相邻时，每个空隙最多放 1 个。

完整讲解 · 例题 · 可练 17 题

一、是什么

骨架有几个空隙

$m$ 个元素排成一行，相邻两个之间有 $m - 1$ 个空隙，再加左右两端，一共 $m + 1$ 个： $□ a □ b □ c □$ 有 $4$ 个。 $m$ 个元素（ $m \geq 2$ ）围成一圈时没有两端，一共只有 $m$ 个空隙。

放回去为什么不重不漏

从一个符合要求的排列里删去特殊元素，得到唯一的骨架和唯一的一组空隙。反过来，骨架、所选的空隙以及每个空隙放哪个元素，共同确定一个排列。插入的元素全部相同时，只需选空隙；元素不同时，还要安排它们分别放在哪里。放进不同空隙的元素之间至少隔着 $1$ 个骨架元素，所以不会相邻。

从空隙里选：组合数

$(k p)$ 表示从 $p$ 个不同的东西里选 $k$ 个、不管先后的选法数， $(k p) = \frac{p ( p - 1 ) \dots ( p - k + 1 )}{k \cdot ( k - 1 ) \dots 1}$ ，例如 $(2 4) = \frac{4 \times 3}{2 \times 1} = 6$ 。 $k > p$ 时选不出来，选法数是 $0$ 。 $k$ 个相同的元素放进 $p$ 个空隙（每隙至多 $1$ 个）有 $(k p)$ 种。 $k$ 个不同的元素要分先后：第 1 个有 $p$ 种放法，第 2 个有 $p - 1$ 种，依次相乘。

骨架本身有几种排法

$m$ 个不同元素排成一行有 $m! = m (m - 1) \dots 1$ 种，全部相同的只有 $1$ 种。围成一圈且旋转后算同一种、镜像算不同时，先让其中 $1$ 个人坐下当基准，其余 $m - 1$ 人排在他后面，有 $(m - 1)!$ 种。

先看一道例题

例 1：由方法数反求个数

$5$ 个相同的白棋子和若干个相同的黑棋子排成一行，黑棋子互不相邻，一共有 $15$ 种排法。黑棋子有多少个？

怎么看出来：

黑棋子互不相邻，所以拿走黑棋子，把白棋子当骨架。方法数已经给出，要反过来求个数。

解：

设黑棋子有 $k$ 个。白棋子相同，骨架只有 $1$ 种，它有 $5 + 1 = 6$ 个空隙。黑棋子相同，只要选出 $k$ 个空隙，排法就定了，排法数是 $(k 6)$ 。逐个计算： $(0 6) = 1$ ， $(1 6) = 6$ ， $(2 6) = 15$ ， $(3 6) = 20$ ， $(4 6) = 15$ ， $(5 6) = 6$ ， $(6 6) = 1$ ； $k > 6$ 时为 $0$ 。等于 $15$ 的是 $k = 2$ 和 $k = 4$ 。

答案：

$2$ 个或 $4$ 个。

二、什么时候想到它

题目里看到	应该想到
几个元素“互不相邻”	拿走它们，排好其余元素，放进不同空隙
某些元素必须在最左端、最右端	这一侧的空隙不能用，先从空隙里去掉
围成一圈且“旋转算同一种”	骨架有 $(m - 1)!$ 种，空隙只有 $m$ 个
特殊元素左右两边的对象有指定要求	只有符合要求的空隙能放，按骨架分类（见进阶“按骨架分类”）
一个元素不能挨着 2 个指定对象	按这 2 个对象是否相邻分类（见进阶“禁邻对象”）
“必须相邻”“恰好隔几个人”	捆成一块，或把 2 人的位置一起定（见进阶“捆绑与紧贴”）

三、怎么用

找出有限制的元素，先拿走。例如 $A, B, C, D, E$ 这 $5$ 张不同的卡片排成一行， $A$ 必须在最左端， $D$ 、 $E$ 不相邻。拿走 $D$ 、 $E$ 。
排骨架。剩下 $A, B, C$ ， $A$ 在最左， $B$ 、 $C$ 的先后有 $2$ 种。
数能放的空隙，并确认每种骨架的个数相同。 $A □ B □ C □$ 有 $3$ 个； $A$ 的左边不能放，否则 $A$ 不在最左端。 $B$ 、 $C$ 换位后还是 $3$ 个。
放回去。 $D$ 有 $3$ 种放法， $E$ 放进另外的空隙有 $2$ 种，共 $3 \times 2 = 6$ 种。
相乘并检验。共 $2 \times 6 = 12$ 种。用另一种算法核对： $A$ 在最左时全部排法有 $4! = 24$ 种，其中 $D$ 、 $E$ 相邻的有 $3! \times 2 = 12$ 种， $24 - 12 = 12$ ，一致。

四、再做一道

例 2：圆桌上不相邻

甲、乙、丙、丁、戊 $5$ 人围圆桌就座，旋转后算同一种，镜像算不同。甲、乙不相邻，有多少种坐法？

怎么看出来：

围成一圈，空隙数和排成一行不同。甲、乙有限制，先拿走。

解：

拿走甲、乙，骨架是丙、丁、戊 $3$ 人围一圈，有 $(3 - 1)! = 2$ 种。一圈 $3$ 人有 $3$ 个空隙。甲有 $3$ 种放法，乙放进另外的空隙有 $2$ 种，共 $6$ 种。总数 $2 \times 6 = 12$ 。检验： $5$ 人围圈共 $4! = 24$ 种，把甲、乙捆成一块后 $4$ 个对象围圈有 $3! = 6$ 种，块内 $2$ 种，相邻的共 $12$ 种， $24 - 12 = 12$ ，一致。

答案：

$12$ 种。

五、容易错在哪

排成一行有 $m + 1$ 个空隙，围成一圈只有 $m$ 个，不要混用。
只有每种骨架的可放空隙数都相同时，才能用一个数直接相乘；个数不同时要分类。
$B$ 、 $C$ 相邻时，它们之间的空隙只算 $1$ 次，不要把不能放的空隙数都算成 $4$ 。
后放的元素可能破坏前面定好的要求：不能插进捆好的块内，也不能放到必须在端点的元素外侧。

进阶：按骨架分类

空隙的个数随骨架变化时，先分类

有时哪些空隙能放，要看骨架长什么样。这时不能用一个数相乘，要按能放的空隙数给骨架分类，每类分别数，再相加。

例 3：星号夹在不同字母之间

$3$ 个 $a$ 、 $2$ 个 $b$ 和 $3$ 颗相同的星号排成一行。每颗星号左右都必须有字母，并且左右两个字母不同。有多少种排法？

怎么看出来：

星号的要求只和字母骨架有关：能放星号的空隙就是字母发生变化的地方，个数随骨架变化，所以分类。

解：

每颗星号左右都是字母，所以星号不在两端，也不相邻，每个空隙至多 $1$ 颗。只看字母，同样的字母连成若干段，能放星号的空隙数等于段数减 $1$ 。要放 $3$ 颗，段数至少是 $4$ 。 $2$ 个 $b$ 至多分成 $2$ 段， $a$ 的段数和 $b$ 的段数相差不超过 $1$ ，所以总段数至多是 $5$ 。段数为 $5$ ：只有 $ababa$ ，有 $4$ 个空隙，选 $3$ 个有 $(3 4) = 4$ 种。段数为 $4$ ：有 $aabab, abaab, baaba, babaa$ 这 $4$ 种骨架，各有 $3$ 个空隙，星号的放法各 $1$ 种，共 $4$ 种。合计 $4 + 4 = 8$ 。

答案：

$8$ 种。

例 4：同类不相邻，还有位置限制

用 $2$ 个 $a$ 、 $2$ 个 $b$ 、 $1$ 个 $c$ 排成一行，相同字母不相邻，且 $c$ 不在两端。有多少种排法？

怎么看出来：

$c$ 只有 $1$ 个却可能要隔开相同字母，所以拿走 $c$ ，看骨架里有几处相同字母挨着。

解：

拿走 $c$ ，骨架是 $2$ 个 $a$ 、 $2$ 个 $b$ 的排列，共 $6$ 种。 $c$ 只能放在内部 $3$ 个空隙，且骨架里相同字母相邻的地方必须由 $c$ 隔开。 $abab$ 、 $baba$ 没有相邻的相同字母， $c$ 放任一内部空隙，各 $3$ 种。 $abba$ 、 $baab$ 有 $1$ 处相同字母相邻， $c$ 只能放在那里，各 $1$ 种。 $aabb$ 、 $bbaa$ 有 $2$ 处， $1$ 个 $c$ 隔不开， $0$ 种。合计 $3 + 3 + 1 + 1 = 8$ 。

答案：

$8$ 种。

进阶：禁邻对象

一个元素不能挨着 2 个对象

元素 $A$ 不能挨着 $B$ 、 $C$ ，不能放的空隙就是 $B$ 、 $C$ 两侧的空隙。 $B$ 、 $C$ 在骨架里不相邻时，这些空隙有 $4$ 个。 $B$ 、 $C$ 相邻时，它们中间那个空隙被算了 $2$ 次，实际只有 $3$ 个。所以要按“ $B$ 、 $C$ 是否相邻”分类。

例 5：禁邻对象和端点限制一起

$A, B, C, D, E, F$ 这 $6$ 张不同的卡片排成一行， $F$ 必须在最右端， $A$ 不能挨着 $B$ ，也不能挨着 $C$ 。有多少种排法？

怎么看出来：

$A$ 有 $2$ 个不能挨着的对象， $B$ 、 $C$ 是否相邻会影响不能放的空隙数，所以分类。

解：

拿走 $A$ ，骨架是 $B, C, D, E, F$ ， $F$ 在最右。 $B, C, D, E$ 的排法共 $4! = 24$ 种。骨架有 $6$ 个空隙， $F$ 右边不能放，还剩 $5$ 个。 $B$ 、 $C$ 相邻的骨架：捆成一块后 $3$ 个对象排 $3! = 6$ 种，块内 $2$ 种，共 $12$ 种。不能放的空隙是 $B$ 左、 $B$ 与 $C$ 之间、 $C$ 右这 $3$ 个（以 $BC$ 次序为例），可放 $5 - 3 = 2$ 个。 $B$ 、 $C$ 不相邻的骨架有 $24 - 12 = 12$ 种。 $B$ 、 $C$ 两侧共 $4$ 个不同的空隙，可放 $5 - 4 = 1$ 个。总数 $12 \times 2 + 12 \times 1 = 36$ 。

答案：

$36$ 种。

进阶：捆绑与紧贴

必须相邻：捆成一块

$A$ 、 $B$ 必须相邻时，把它们捆成一块当 $1$ 个元素，块内再排 $2$ 种。块内部那个位置不是空隙，后面放别的元素不能插进去，否则就拆开了。如果块只能放在某些位置（比如不能跨过午休），要先数块的位置。

恰好隔几个人：把两人的位置一起定

$n$ 人排成一行，要求 $A$ 、 $B$ 之间恰有 $k$ 人（ $0 \leq k \leq n - 2$ ）。 $A$ 、 $B$ 的位置相差 $k + 1$ ，左边那个位置有 $n - k - 1$ 种取法， $A$ 、 $B$ 谁在左有 $2$ 种，其余 $n - 2$ 人排 $(n - 2)!$ 种，共 $2 (n - k - 1) \cdot (n - 2)!$ 种。

例 6：捆绑、端点和不相邻

甲、乙、丙、丁、戊、己 $6$ 人排成一行，戊在最左端，甲、乙必须相邻，丙、丁不相邻。有多少种排法？

怎么看出来：

相邻和不相邻同时出现时，先捆绑，后插空。甲、乙块内部不能当空隙。

解：

拿走丙、丁，把甲、乙捆成一块，块内 $2$ 种。骨架是戊、甲乙块、己，戊在最左，块和己的先后有 $2$ 种。空隙是戊右边、中间、最右端，共 $3$ 个；戊左边不能放，块内部也不能放。丙有 $3$ 种放法，丁放进另外的空隙有 $2$ 种。总数 $2 \times 2 \times 3 \times 2 = 24$ 。

答案：

$24$ 种。

例 7：两人之间的人数是奇数

$6$ 人排成一行，甲、乙之间的人数是奇数。有多少种排法？

怎么看出来：

$6$ 人时甲、乙之间最多 $4$ 人，奇数只有 $1$ 和 $3$ 。把两人的位置一起定。

解：

之间恰有 $1$ 人：两人的位置相差 $2$ ，左边的位置可取 $1, 2, 3, 4$ ，共 $4$ 种，谁在左 $2$ 种，其余 $4$ 人排 $4! = 24$ 种，共 $4 \times 2 \times 24 = 192$ 种。之间恰有 $3$ 人：位置相差 $4$ ，左边的位置可取 $1, 2$ ，共 $2 \times 2 \times 24 = 96$ 种。两类互不重叠，合计 $192 + 96 = 288$ 。

答案：

$288$ 种。

进阶：固定次序的插入

原有次序不变、新元素可以相邻：逐个插入

已排好的元素次序不动，再插入几个不同的新元素，而且新元素可以挨在一起时，每插入一个，空隙就多一个。 $4$ 个元素有 $5$ 个空隙，插入第 1 个新元素有 $5$ 种，这时有 $5$ 个元素、 $6$ 个空隙，插入第 2 个有 $6$ 种，共 $5 \times 6 = 30$ 种。

圆桌上交替就座

$n$ 男 $n$ 女（ $n \geq 2$ ）围圆桌交替就座，旋转算同一种、镜像算不同。先让男生坐好，有 $(n - 1)!$ 种，这时恰好有 $n$ 个空隙，每个空隙必须坐 $1$ 位女生，有 $n!$ 种，共 $(n - 1)! \cdot n!$ 种。

真题

按这个方法练 · 17 题

收起并返回方法目录

选唯一参数表示，再按范围分层计数

用参数生成对象时，要同时证明每个合法对象都能生成、每个对象只生成一次。可先规定递增次序或选择唯一根，再用范围较小的参数作外层计数。

完整讲解 · 例题 · 可练 26 题

一、是什么

整数等差三项

递增整数等差三项写成 $a, a + d, a + 2 d$ ， $d \geq 1$ 。若各项在 $1$ 到 $N$ ，则 $1 \leq d \leq ⌊(N - 1) /2 ⌋$ ，固定 $d$ 后有 $N - 2 d$ 个首项。若题目把反向数列另算，还需说明是否要乘二。

整数等比需规范化

正整数递增等比三项，可先写公比为互素正整数之比 $p / q > 1$ 。若首项为 $x$ ，第三项 $x p^{2} / q^{2}$ 为整数，且 $p, q$ 互素，故 $q^{2}$ 整除 $x$ 。于是可整理为 $t q^{2}, tpq, t p^{2}$ 。互素表示保证公比唯一， $t$ 再由首项确定；不能未经证明把公比限定为整数。

根生成的重复

一个方程有两个可选整数根时，按根生成可能把同一方程数两次。可规定取较小根作参数，重根另单列。只有证明双向可恢复，才可把参数个数当对象个数。

先看一道例题

例 1：十以内递增等差三项

从 $1, \dots, 10$ 中选三个数构成递增等差数列，有多少个？

怎么看出来：

公差是唯一正整数参数。

解：

$d = 1, 2, 3, 4$ 时首项分别有 $8, 6, 4, 2$ 种，共 $20$ 。每组三项的首项和公差均唯一，因此没有重复，也未漏合法组。

答案：

$20$ 。

二、什么时候想到它

题目里看到	应该想到
求整数数列条数	先规定方向和规范参数
嵌套整数不等式	固定外层参数后数闭区间整数
由某个根构造方程	检查同方程是否由多根重复生成

三、怎么用

确定对象是否有序及标准表示。
从最大末项推参数范围。
固定外层参数数内层。
证明生成与恢复均唯一。

四、再做一道

例 2：两个整数根且小根唯一

首一二次多项式的两个不同整数根都在 $1, \dots, 5$ 。有多少个这样的多项式？

怎么看出来：

按较小根分层。

解：

较小根为 $1, 2, 3, 4$ 时，大根各有 $4, 3, 2, 1$ 种，共 $10$ 。每对根唯一决定 $(x - r) (x - s)$ ，反过来根集唯一，所以每个多项式计一次。

答案：

$10$ 。

五、容易错在哪

递增三项和正负公差的有序数列是不同的计数对象。
参数能够生成对象还不够，必须证明能唯一恢复参数。

真题

按这个方法练 · 26 题

收起并返回方法目录

只记下一步所需的末位状态

逐位限制的计数不必保留整个前缀。状态是决定下一步合法选择所需的全部信息：相邻两位约束通常只记末位，三位窗口约束至少记末两位。

完整讲解 · 例题 · 可练 8 题

一、是什么

状态的转移

令 $f_{k} (s)$ 为长度 $k$ 、末状态为 $s$ 的合法串数。每个合法新字符使状态转到 $t$ ，将 $f_{k} (s)$ 累加到 $f_{k + 1} (t)$ 。不同来源可以相加，但同一串必须有唯一的“删去末字符”来源。

固定中间位

长度三的串若左右条件只分别涉及中间位，可固定中间位 $b$ ，左右选择数相乘，再对 $b$ 求和。若左右还要求互不相同，就不能直接相乘。

数码重数和首位

用余数代替实际数字时，还要记每类剩余个数；相同余数不等于同一个数字。若数的是整数而不是固定长度字符串，首位不能为零。把每类数字排列数乘回前，要确保类间没有额外限制。

先看一道例题

例 1：不含连续一的二进制串

长度为 $4$ 的 $0, 1$ 字符串中，不含连续两个 $1$ 的有多少个？允许首位为零。

怎么看出来：

记末位为零和一的两种状态。

解：

长度一时计数为 $(1, 1)$ 。下一位为零可接任意旧串，下一位为一只接末位零，所以依次是 $(2, 1), (3, 2), (5, 3)$ 。合计 $5 + 3 = 8$ 。

答案：

$8$ 。

二、什么时候想到它

题目里看到	应该想到
条件只涉及相邻位置	按末位计数
左右分别依赖中间位	固定中间位再相乘
有三位窗口或数码不可重复	扩大状态，加入剩余重数

三、怎么用

明确首位限制和能否重复。
选足够判断下一步的最小状态。
逐状态列合法转移并累加。
合计终态，核没有漏串或重复。

四、再做一道

例 2：固定中间数码

三位数各位来自 ${1, 2, 3}$ ，允许重复，且相邻两位之差的绝对值均为 $1$ 。有多少个？

怎么看出来：

固定十位后左右独立。

解：

十位为 $1$ 或 $3$ 时，百位、个位都只能为 $2$ ，各 $1$ 个。十位为 $2$ 时，两边各有 $1, 3$ 两种选法，得 $4$ 个。共 $1 + 4 + 1 = 6$ ，首位均非零。

答案：

$6$ 。

五、容易错在哪

状态必须记全窗口所需信息，仅见相同末位不一定能合并状态。
余数相同的数字仍有重数；整数的首位限制必须单列。

真题

按这个方法练 · 8 题

收起并返回方法目录

置换按循环或最大元拆开，先证结构再递推

置换是把 $1, \dots, n$ 一一对应到自身的双射。沿 $i \mapsto π (i)$ 反复走会回到起点，所得互不相交的循环称为循环分解； $π (i) = i$ 叫不动点。

完整讲解 · 例题 · 可练 7 题

一、是什么

循环的位移下界

一个长度为 $r$ 的循环经过 $r$ 个不同整数。从最小走到最大再绕回，绝对位移总和至少为跨度的两倍，而跨度至少 $r - 1$ ，故循环贡献至少 $2 (r - 1)$ 。全置换的位移和为各循环贡献之和。

禁止模式的含义

避免模式 $231$ 指不存在指标 $i < j < k$ 使 $π (k) < π (i) < π (j)$ 。在最大元 $n$ 处分左右：若有左值大于右值，它与中间的 $n$ 就构成 $231$ ，故每个左值都小于每个右值。

结构封闭后才递推

避免 $231$ 时，左右各自也必须避免此模式；反过来，左右值域分离且各自避免，就不会产生跨段模式。若左侧长度为 $k$ ，它只能用最小 $k$ 个数，右侧用剩下数。记数量为 $C_{n}$ ，得到 $C_{0} = 1, C_{n} = \sum_{k = 0}^{n - 1} C_{k} C_{n - 1 - k}$ 。带交替等额外约束时要重新验证封闭性，不能直接照搬。

先看一道例题

例 1：四元错排的位移最小值

$π$ 是 ${1, 2, 3, 4}$ 的无不动点置换，求 $\sum_{i = 1}^{4} ∣ π (i) - i ∣$ 的最小值。

怎么看出来：

循环类型只有两个二循环或一个四循环。

解：

两个二循环各至少贡献 $2$ ，总计至少 $4$ ；一个四循环至少贡献 $6$ 。交换相邻的 $(1, 2)$ 、 $(3, 4)$ 得置换 $(2, 1, 4, 3)$ ，位移和为 $4$ ，达到下界。

答案：

$4$ 。

二、什么时候想到它

题目里看到	应该想到
无不动点且问位移和	分成不交循环
禁止三元相对大小模式	在最大元处分左右
要写计数递推	先证明子问题类型保持

三、怎么用

写清置换约束和所求量。
选循环或最大元作拆分。
证明贡献下界或子类封闭。
递推计算，并穷尽取等结构。

四、再做一道

例 2：避免二三一的三元置换

求避免模式 $231$ 的三元置换个数。

怎么看出来：

用最大元分拆递推，再枚举核对。

解：

$C_{0} = 1, C_{1} = 1, C_{2} = 2$ ，故 $C_{3} = C_{0} C_{2} + C_{1} C_{1} + C_{2} C_{0} = 2 + 1 + 2 = 5$ 。三元共六种，只有 $231$ 自己含该模式，所以也得到 $5$ 。

答案：

$5$ 。

五、容易错在哪

结构递推必须证明跨段不会新增禁止模式。
只造一个极值方案不足以证明最小值，还要覆盖全部循环类型。

真题

按这个方法练 · 7 题

收起并返回方法目录

误区对照

容易误以为

用数字 $0, 0, 1, 2$ 各一次排四位数，直接用 $4! /2! = 12$ 。

应当这样想

该式数出含前导零的四位串；首位为零的串有 $3! = 6$ 个，故四位数只有 $12 - 6 = 6$ 个。

为什么

多重排列只处理相同数字的重数，不自动处理首位非零。

容易误以为

三个相同 $A$ 形成两个内部空隙，放入两个不相邻的相同 $B$ 只有一种。

应当这样想

若无首尾限制，应包含两端，共四个空隙；每隙至多放一个 $B$ ，选二空隙得 $(2 4) = 6$ 种，删去 $B$ 可唯一复原。

为什么

插空的可用位置由原题限制决定，不能凭图省略首尾。

概念自测

先想清楚，再确认判断。这些自测只帮助辨清概念，不计入真题做对率。

真题 · 123 道

从易到难排列。圆点表示你在这台设备上的做题情况：绿色做对、黄色部分做对、红色没做出。