初赛专题（五）：组合计数 —— 两大原理、排列组合与四大换皮模型

本讲定位：CSP-J 初赛系列的数学主峰之一。七年真题统计（见 cspj-exam-analysis-2019-2025.md）：组合计数七年全勤、合计 28 分，是选择题最稳的基本盘，每年 4~6 分从未爽约。它的出题方式是”换皮轮考”——捆绑、插空、隔板、抽屉、容斥这几个模型轮流披上新故事（车牌、分名额、组队、选代表），模型认出来了就是送分，认不出来就干瞪眼，所以本讲按模型组织，每个模型练到”报出名字、写出式子”。

组合计数是纯手算专题，程序题不考它——但第 5.3 节的网格路径会顺手写一段递推打表程序，让”公式算”和”程序算”互相验证，这既是查错手段，也是第 09 讲读 DP 程序的前菜。

前置知识：乘法与约分（真的没有别的了）。

适合对象：CSP-J 初赛。标注 ⭐ 的小节为进阶内容，第一遍学习可以跳过。

1. 加法原理与乘法原理

一切计数题的地基就两句话：

• 加法原理（分类）：完成一件事有 $k$ 类办法，各类互不重叠，方法数相加。
• 乘法原理（分步）：完成一件事分 $k$ 步，每步独立选择，方法数相乘。

判别口诀：“或者”就加，“然后”就乘。做任何计数题的第一个动作都是问自己：我是在分类，还是在分步？

例 1：从 A 城到 B 城有 3 趟高铁或 2 趟航班，走法 $3 + 2 = 5$ 种（分类）；从 A 经 B 到 C，若 B 到 C 有 4 趟车，则 A→B→C 共 $5 \times 4 = 20$ 种（分步）。

例 2（对称计数，2019 车牌题的原型）：某车牌由 6 位数字组成，要求是回文（正读反读相同），有多少种？——回文的后一半被前一半唯一确定，自由的只有前 3 位：$10^3 = 1000$ 种。对称/回文类计数的通用心法：只数自由的那一半，另一半不产生选择。

例 3（每步选择数会变）：4 位密码，要求相邻两位不同：第 1 位 10 种，以后每位不能与前一位相同、各 9 种，共 $10 \times 9^3 = 7290$。乘法原理里每步的选择数允许依赖前面的结果个数，只要”无论前面怎么选、本步的选择数都一样”就能乘。

2. 排列数与组合数

2.1 定义与手算

从 $n$ 个不同元素中取 $m$ 个：

$$ A_n^m = n(n-1)(n-2)\cdots(n-m+1) = \frac{n!}{(n-m)!} \qquad \binom{n}{m} = \frac{A_n^m}{m!} = \frac{n!}{m!\,(n-m)!} $$

• 排列 $A$：取出来还要排顺序（站队、编号、排名）。
• 组合 $\binom{n}{m}$（也记 $C_n^m$）：只管选了谁，不管顺序（选代表、握手、连线）。

判别口诀：把选出的两个元素互换，算不算新方案？算，用 $A$；不算，用 $\binom{n}{m}$。

手算规矩：先约分再乘，绝不先算阶乘。$\binom{10}{3} = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120$——分子分母各写 $m$ 个因子，上下消干净再乘，两位数乘法解决一切初赛组合数。