第15章　排列组合基础

1. 加法原理与乘法原理

• 分类：互不重叠的情况相加。
• 分步：多个步骤都必须完成，选择数相乘。
• 排列：从 $n$ 个不同对象中选 $r$ 个并排序，$A_n^r=n!/(n-r)!$。
• 组合：只选不排序，$C_n^r=n!/[r!(n-r)!]$。

判断关键：交换两个选中对象，是否算新方案？若算，顺序有意义。例如甲、乙、丙 3 人中选 2 人组成不分职位的小组，有 $C_3^2=3$ 种；选队长和队员则有 $A_3^2=3\times 2=6$ 种，因为甲当队长、乙当队员与乙当队长、甲当队员是不同方案。

2. 分类、分步与从特入手

固定顺序的题先定位特殊位置；多个限制时优先安排最受限制者。可把“至少一个”“不能全选”用全部减不符。

若 5 个固定次序任务中，两个指定任务不能在首尾，可先安排这两个任务的位置，再排其余任务；或先排全部再减去违反情形。两法都要避免重复扣除。

3. 简单枚举和分情况

当对象很少、约束强时，列表枚举比公式更省事。列情况时确保互斥且覆盖全部可能；可固定某一个变量，按其取值分支。涉及 0-1 序列的“前缀分数始终满足条件”，可转为路径计数或递推。