19.5
排列组合综合计数
综合使用分类、分步、正难则反和位置分析解决计数问题。
本文章目录
01 · 出发点
综合计数先设计结构，再进行计算
真实计数问题很少只出现一种原理。相邻限制、指定对象、至少一个等条件会迫使我们同时使用分类、分步、排列、组合以及间接计数。
综合计数的目标不是寻找最长的公式，而是建立一个不重不漏的方案模型。先处理限制最强的部分，常能把复杂问题化为几个熟悉的基本模型。
02 · 概念
常用计数策略
特殊元素优先、特殊位置优先、相邻元素捆绑、不相邻元素插空、顺序固定除以排列数，都是对方案结构的重新编码。每种策略都必须说明编码与原方案之间是一一对应。
当正面满足条件的方案难以直接构造时，可以先算所有方案，再减去不满足条件的方案。间接计数尤其适合“至少一个”“不能全是”等条件。
03 · 方法
限制条件下的决策顺序
- 01
把条件翻译成位置、元素、相邻或数量限制，识别最强约束。
- 02
选择分类、捆绑、插空或正难则反等模型，并写清每步选择数。
- 03
用小规模列举或另一种方法复核，检查边界和重复。
04 · 例题
把方法落到具体问题
甲、乙和另外 3 人排成一列，要求甲、乙不相邻，共有多少种排法？
解
- 1
先计算 5 人任意排列，共有 5!=120 种。
- 2
计算甲、乙相邻的排法：把两人捆成一个整体，与另外 3 人共 4 个对象，有 4! 种排列。
- 3
捆绑内部甲、乙有 2 种顺序，所以相邻排法有 2×4!=48 种。
05 · 辨析
容易忽略的条件与边界
回看
本节小结
- 综合计数的核心是建立不重不漏的一一对应模型。
- 限制最强的元素或位置通常应优先处理。
- 正难则反、捆绑和插空都需要明确适用条件。