第四十二课：排列组合解题技巧③——至少、至多与排除法
本课的重点不是让同学们背更多公式，而是学会一个非常重要的思维：
正面不好算，就从反面算。
也就是我们经常说的：
总数−不满足的数量
对于CSP-J初赛来说，这种“分类、补集、排除”的思想非常重要。
一、先玩一个小游戏：数一数有多少种？
假设有：
A B C D E
5个人排成一排。
总共有：
5!
种。
也就是：
120
种。
现在增加一个条件：
A和B不能相邻。
怎么办？
二、第一反应：直接数“不能相邻”
如果直接数：
A、B不能相邻的排列有多少种？
孩子可能会发现：
A _ B
_ A B
A B _
……
情况越来越多。
很麻烦。
这时候老师应该问：
那我们反过来数行不行？
也就是：
A、B不能相邻
= 所有排列 – A、B相邻的排列
这就简单多了。
三、第一步：先算总数
5个人随便排列：
5! = 120
四、第二步：计算A、B相邻的情况
把A、B捆起来：
[AB] C D E
一共4个整体：
4!
A、B内部有：
AB
BA
两种：
2!
所以：
4! × 2! = 48
五、第三步：用总数减掉
总数：
120
A、B相邻：
48
所以A、B不相邻：
120 − 48 =72
六、这就是“排除法”
我们没有直接计算：
不相邻有多少种。
而是：
所有情况
↓
减去
↓
不允许的情况
也就是：
符合条件 = 总情况 − 不符合条件
这就是本课要学习的最重要思想。
七、同学们要理解：为什么“反过来”更容易？
因为：
“相邻”很好算。
一旦相邻：
A B
就可以：
[AB]
捆成一个整体。
但是：
“不相邻”不好直接数。
因为它包含大量零散情况。
所以：
相邻
容易数
不相邻
直接数困难
于是：
不相邻 = 总数 − 相邻
八、给同学们一个生活中的例子
班里有100张卡片。
其中：
-
60张红色
-
40张蓝色
如果老师问：
不是红色的卡片有多少张？
当然可以直接数蓝色：
40
但也可以：
100 − 60 = 40
这就是最简单的补集思想。
九、“补集”到底是什么？
大家可以把它理解成：
一个问题的“反面”。
例如：
| A相邻B | A不相邻B |
| 至少1个 | 1个都没有 |
| 至少2个 | 少于2个 |
| 全部满足 | 至少有一个不满足 |
| 不出现某情况 | 出现某情况 |
因此：
原问题 + 反面 = 全部情况
所以：
原问题 = 全部情况 − 反面
十、第二个核心：至少
“至少”是CSP-J初赛特别喜欢考的关键词。
例如：
至少有一个女生。
“至少一个”是什么意思？
可能是：
1个
2个
3个
4个
……
如果女生很多，直接分类会非常麻烦。
但是我们可以换一个角度：
至少一个 = 不是一个都没有。
所以：
至少一个 = 总数 − 一个都没有
十一、经典例题：至少有一个红球
盒子中有：
5个红球
3个蓝球
现在选择2个球。
问：
至少选择到1个红球，有多少种选法？
方法一：直接分类
至少1个红球，有两种情况：
情况1
选1个红球+1个蓝球：
情况2
选2个红球：
所以：
十二、但是还有更漂亮的方法
总共从8个球中选2个：
总数：
28
不满足“至少一个红球”的情况是什么？
一个红球都没有。
也就是：
两个球全部是蓝球。
所以：
因此：
十三、为什么“至少一个”特别适合补集？
因为：
“至少一个”看起来很多情况。
比如：
1个
2个
3个
……
而它的反面特别简单：
0个。
所以：
至少1个 = 总数 − 0个
这是非常重要的数学思想。
十四、第三个关键词：至多
“至多” 与 “至少” 正好相反方向。
例如：
至多2个
意思是：
0个
1个
2个
而不是：
2个以上
一定要看清楚。
十五、“至少”和“至多”的数轴
可以画成：
0 1 2 3 4 5 6
|—|—|—|—|—|—|
至少2个：
●────────────→
2 3 4 5 6
至多2个：
←────────●
0 1 2
所以：
至少2个：2、3、4……
至多2个：0、1、2
十六、特别容易混淆的三个词
大家一定要区分：
至少2个
>= 2
至多2个
<= 2
恰好2个
== 2
可以记：
至少：不能比它少。
至多：不能比它多。
恰好：就是这个数。
十七、“至少一个”和“至少两个”有什么区别？
至少一个
反面：
0个
所以特别适合补集：
总数 − 0个
至少两个
反面是：
0个
或者
1个
所以：
至少2个=总数 −0个 −1个
这也是一个非常重要的规律。
十八、例如：至少2个红球
假设：
5个红球
4个蓝球
选3个球。
问：
至少选到2个红球，有多少种？
总数：
反面：
红球少于2个。
也就是：
0个红球
三个全是蓝球：
1个红球
一个红球+两个蓝球：
所以：
所以，至少选到2个红球的选法，就等于从9个球中任选3个的总数，减去“0个红球”和“1个红球”这两种不满足要求的情况：
其中， 表示从9个球中任选3个的总数； 表示3个全是蓝球（0个红球）的情况； 表示恰好1个红球、2个蓝球的情况。把这两类“红球少于2个”的情况从总数中减掉，剩下的就正好是“至少2个红球”的选法。
这就是：
至少2个 = 总数 – 0个 – 1个
十九、“至少”题的通用方法
看到：
至少K个
首先想到：
总数 − (0个+1个+⋯+(K−1)个)
例如：
至少1个
总数 − 0个
至少2个
总数 − (0个+1个)
至少3个
总数 − (0个+1个+2个)
二十、“至多”题怎么办？
例如：
至多2个红球。
那么直接分类：
0个
1个
2个
即可。
所以：
至多2个= 0个 + 1个 + 2个
当然，如果直接分类很多，也可以考虑补集：
至多2个 = 总数 − 至少3个
关键的不是死记，而是：
哪边更容易算，就算哪边。
二十一、这句话非常重要
给学生强调一下：
数学题不是一定要“正着算”。
哪条路短，就走哪条路。
例如：
正面：
1个 + 2个 + 3个 + 4个 + 5个
非常麻烦。
如果反面只有：
0个
那么就算：
总数−0个
就非常漂亮。
二十二、第四个技巧：排除重复
除了补集，“排除法”还有一种很常见的使用方式：
先把所有情况算出来，再减去不合法的情况。
例如：
4位数字密码，数字可以重复，但是第一位不能是0。
先不管限制
每一位：
10
种。
总数：
10^4=10000
再排除第一位是0
第一位固定：
0
后面三位各有10种：
10^3=1000
所以合法密码：
二十三、其实也可以直接算
第一位不能0：
9
种。
后面：
10×10×10
所以：
两种方法都可以。
这告诉大家：
排除法不是唯一方法，而是一种解决复杂限制的工具。
二十四、什么时候优先考虑排除法？
我们有一个非常实用的判断标准：
如果题目是：
“不能……”
先想：
总数−违反条件的情况
如果题目是：
“至少……”
先想：
总数−少于要求的情况
如果题目是：
“至多……”
先看看：
直接分类是不是更简单？
二十五、一个经典综合题
例题
6个人排成一排。
要求：
A、B不能相邻。
求排法数量。
第一步：总数
6!
第二步：A、B相邻
捆绑：
[AB] C D E F
5个整体：
5!
AB内部：
2!
所以：
5!×2！
第三步：排除
二十六、把两种方法联系起来
你会发现：
上一课
A、B必须相邻
使用：
捆绑法\\boxed{捆绑法}
本课
A、B不能相邻
使用：
总数 − A、B相邻
而“相邻”这一部分：
还是使用上一课的捆绑法。
所以知识不是一课一课割裂的。
而是：
第41课：捆绑
↓
第42课：补集
↓
A、B不能相邻
↓
总数 – A、B相邻
↓
相邻部分再用捆绑法
这就是我们上课，希望大家形成的知识网络。
二十七、一个非常经典的“至少”排列题
5个人排队：
A B C D E
问：
A、B至少有一个站在最左边或最右边。
这种题如果直接分类，很容易重复计算。
这时候可以考虑：
反面是什么？
反面是：
A、B都不在两端。
两端只能放其他3个人。
这时候再计算反面。
这类题会涉及：
补集 + 特殊位置
正是考试很喜欢的综合思维。
方法：
“至少有一个站在最左或最右”的反面是A、B都不在最左、也不在最右（即A、B都站在中间3个位置）。
计算5个人的总排列数： 5!=5×4×3×2×1=120 种
计算不符合要求的排列数（A、B都不在两端）：
-
两端位置只能由C、D、E三人排列：
-
从3人中选2人站两端，排列数为 3×2=6 种；
-
剩下3个位置（含中间3个位置）由剩下的3人（含A、B）全排列：3!=6 种；
-
因此不符合要求的总排列数为 6×6 = 36 种。
符合要求的排列数 = 总排列数 – 不符合要求的排列数：
120−36 = 84 种
二十八、为什么补集特别适合程序阅读题？
考试有可能，不一定直接让同学直接计算。
有时候会给出程序：
ans = total – bad;
然后问：
ans表示什么？
如果同学理解：
总数 − 不合法情况
就能快速判断程序的数学意义。
所以：
数学思想最终会反过来帮助程序阅读。
二十九、本课要掌握的关键词
看到这些词，一定要敏感：
“至少”
想到：
>=
“至多”
想到：
<=
“恰好”
想到：
==
“不能……”
想到：
补集/排除
“不相邻”
想到：
插空或补集
“至少一个”
尤其要想到：
总数−0个
三十、CSP-J考场“反粗心”检查表
排列组合题做到最后，同学们要强制问自己5句话：
① “至少”到底是 >= 还是 <= ？
② “至多”有没有把0算进去？
③ 有没有重复计算？
④ 我算的是正面，还是反面？
⑤ 如果用了减法，我减掉的到底是什么？
最后这一条特别重要。
例如：
5! − 4!
一定要搞清楚：
5!是什么？
4!是什么？
为什么可以相减？
会解释，才是真的会。
三十一、本课知识地图
排列组合
│
┌─────────┴─────────┐
↓ ↓
正面计算 反面计算
│ │
分类 / 分步 补集 / 排除
│
┌───────────┼───────────┐
↓ ↓ ↓
不能 至少 至多
↓ ↓ ↓
总数- 总数- 分类
相邻情况 不足情况 或补集
三十二、把40~42课连成一个整体
现在同学们应该形成这样一个完整的“排列组合工具箱”：
| 或者 | 加法 |
| 然后、并且 | 乘法 |
| 可以重复 | 可重排列 |
| 必须相邻 | 捆绑法 |
| 不能相邻 | 插空法 / 补集 |
| 固定位置 | 定位 |
| 至少一个 | 总数 − 0个 |
| 至少K个 | 总数 − 0～K−1个 |
| 至多K个 | 直接分类或补集 |
| 不能出现某情况 | 总数 − 不合法情况 |
三十三、考试的“排列组合三十秒决策法”
考试看到题目后，先别算。
先在脑子里过一遍：
① 是“或者”还是“然后”？
↓
加还是乘？
② 顺序重要吗？
↓
排列还是组合？
③ 能重复吗？
↓
选择数会不会减少？
④ 有没有特殊限制？
↓
相邻？不相邻？固定位置？
⑤ 出现“至少/至多/不能”了吗？
↓
要不要考虑补集？
然后才开始计算。
三十四、今天的核心口诀
🪄 本课排列组合魔法口诀
至少一个，不如算没有；
至少两个，反面算到一个；
不能相邻，先想总数；
减掉相邻，问题变简单；
至多几个，可以直接分类；
哪边情况少，就从哪边算！
最重要的一句话：
“正面难算，就算反面；总数减去不要的，就是我要的。”
三十五、课后练习
建议本课结束后给学生做这8道题，重点不是速度，而是先判断方法，再计算。
1
6个人排队，A、B不能相邻，有多少种？
答案：
6!−5!×2!=480
2
5个人排队，A、B必须相邻，有多少种？
答案：
4!×2!=48
3
从8个球中选择2个，至少有1个红球。假设5红3蓝。
答案：
4
“至少3个”是什么意思？
答案：
3个及以上
5
“至多3个”是什么意思？
答案：
0、1、2、3个
6
“恰好3个”是什么意思？
答案：
正好3个
7
一个4位数字密码允许重复，但第一位不能为0，有多少种？
答案：
9×10×10×10=9000
8
一个4位数字密码允许重复，先算所有情况，再减去第一位为0的情况，下面哪个表达式正确？
答案：
A
因为：
10^4
是所有密码，而第一位固定为0时，后面还有3位，每位10种：
10^3
