分类加法与分步乘法原理

有两件不同上衣甲、乙，三条不同裤子 1、2、3。每套由一件上衣和一条裤子组成。不限制搭配时有几套？若甲不能配裤子 3，又有几套？

学习前置：整数四则运算、有序数对、三位数和奇偶数。学习目标：说清完整结果；判断分类是否互斥且穷尽；检查每一步的选择数是否随之前的结果变化。本页S班难度为项目编排，不代表当地官方课纲。

分类加法：每一类都能独立完成整件事

把所有合法结果分成若干类，每个结果恰好归入一类。第i类有nᵢ个结果，则总数N=n₁+n₂+…+nᵣ。这里r为类别数，nᵢ为非负整数。互斥保证不重，穷尽保证不漏。

分步乘法：每个完整结果有唯一的选择记录

一件事要依次经过r步。第1步有m₁种选择；无论之前怎么合法选择，第2步总有m₂种……则N=m₁×m₂×…×mᵣ。每组合法选择记录必须唯一对应一个完整结果，不能遗漏或重复。

为什么成立？把第一步的每个选择看成一根树枝。若每根树枝都延伸出同样多的后续树枝，逐层展开后的叶子数就是连乘。叶子代表完整结果，中间节点还没有完成任务。

依赖并不自动否定乘法，数量不统一才需要调整

选正、副组长，副组长不能是已选正组长，候选人确实依赖前一步；但4人中选正组长后，总有3个副组长候选，所以仍为4×3=12。这里讨论的是计数，不能把“概率独立”作为乘法原理的必要条件。

分支数不统一：N = 各分支完整结果数之和

例如甲只能配两条裤子、乙能配三条：N=1×2+1×3=5。不同类型分支内用乘法，各类型分支间用加法。先画浅层选择树，再选较少分支的分类位置。

• 只看“或者、并且”不够。必须先明确完整结果。“选上衣并选裤子”通常是分步；“甲类或乙类穿搭”是否相加，还要验证类是否重叠。
• 重叠反例：数1至10中偶数或3的倍数，偶数5个，3的倍数3个，6在两类中。5+3多算一次，实际7个。本页先强调互斥分类，重叠集合的系统处理见容斥原理。
• 遗漏反例：按三位偶数个位2或4分类会漏掉个位0的一整类。
• 记录不唯一反例：4人中选2名无职务差别的代表，先选甲再选乙与先选乙再选甲表示同一对；4×3会把每一对算两次，不能把它当作最终答案。
• 零种与空操作：某个分支无合法后续时贡献0，不把它记成1。允许“什么都不选”时，空选择可是一种结果，但必须由题意允许。

解题自检：①一个完整结果是什么？②分类是否互斥并覆盖全部？③每步可选数量是否对所有前序选择都成立？④每条选择记录与结果是否一一对应？⑤能否用小规模枚举核验？

点击章节标题定位播放；文字稿默认全部展开。