- 准确陈述计数基本原理（乘法原理），并指出其成立的条件；
- 会用树形图枚举两阶段过程的所有结果，说明叶子数与各层分枝数的关系；
- 能运用推广到 \(k\) 个阶段的乘法原理解决套餐、委员会、牌照、掷骰等计数问题，正确计算 \(m^n\) 型结果总数；
- 能辨识"某一阶段的选择数依赖于前面结果"的情形，改用分类相加的方法计数，避免误用乘法原理。
1. 原理的陈述：从一份菜单说起
第 1 章的任务是"数清楚"一个随机试验究竟有多少种可能结果。第 2 章将会看到：在结果等可能的样本空间中，事件的概率恰好等于"有利于该事件的结果数除以结果总数"，因此计数是概率计算的第一项基本功。整个组合分析大厦的地基，是一条陈述起来毫不起眼、威力却极其巨大的原理。
某餐厅的套餐由前菜、主菜、甜点各一道组成。菜单上前菜有 3 种、主菜有 5 种、甜点有 2 种。问一共可以配出多少种不同的套餐？
例 1 中反复出现的关键句是"无论前面的结果如何"。把它提炼成一般命题，就得到本节的核心定义。
若某个过程由两个阶段(stage)组成：第一阶段共有 \(n_1\) 种可能结果，并且无论第一阶段的结果是什么，第二阶段都恰有 \(n_2\) 种可能结果，则整个过程共有 \[ n_1 \times n_2 \] 种可能结果。
该原理又称乘法原理(multiplication rule)。直观理解：想象一张 \(n_1\) 行、\(n_2\) 列的表格，第 \(i\) 行第 \(j\) 列的格子对应"第一阶段取第 \(i\) 种结果、第二阶段取第 \(j\) 种结果"的复合结果；由于两个阶段互不干扰，格子恰有 \(n_1 n_2\) 个，且两两不同。本节图 2 的骰子网格正是这张表格的具体化身。
两个阶段显然不够用，所幸原理可以直接推广到任意多个阶段。
设某个过程由 \(k\) 个阶段依次完成。若对每个 \(i=1,2,\ldots,k\)，无论前 \(i-1\) 个阶段的结果如何，第 \(i\) 个阶段都恰有 \(n_i\) 种可能结果，则整个过程共有 \[ n_1\, n_2 \cdots n_k \] 种可能结果。
2. 树形图：把原理画出来
树形图(tree diagram)是理解乘法原理最直观的工具：从根出发，第一阶段的每一种选择引出一条枝；每个枝端再按第二阶段的选择继续分枝，如此层层展开，直到最后一层——每一片叶子对应整个过程的一个完整结果，叶子总数就是结果总数。把例 1 的菜单简化（只保留前菜与甜点两个阶段：3 种前菜 × 2 种甜点），图 1 画出了完整的树。
树形图的价值在于"不重不漏"：每片叶子恰对应一条从根出发的路径，数叶子就是数结果。在结果不超过几十个的小型问题中，它可以充当完整的枚举与检验工具；但当阶段数或每阶段的选择数增大时，叶子数按乘积（往往按指数）爆炸——掷 3 颗骰子有 216 片叶子，8 位密码约有 \(62^8\approx 2.2\times 10^{14}\) 片——此时必须放弃逐片数叶子，直接依靠原理本身。
3. 应用：委员会、牌照与骰子
下面三个例子展示乘法原理的典型用法：识别阶段、核实各阶段选择数是否与前面无关、然后连乘。
某协会由 10 名女性成员与 12 名男性成员组成。现要从女性、男性中各选 1 人组成一个两人委员会，共有多少种可能的组成方式？
某地机动车牌照编号规则为：首位是一个英文字母，后面接 6 个数字（数字允许重复）。按此规则共能编出多少个不同的牌照号码？
连续掷 3 颗骰子（或同一颗骰子连掷 3 次），把依次得到的点数记录成一个三元组。这样的结果共有多少种？
形如 \(m^n\) 的计数在本教程中随处可见，下表汇总了最常见的几种，建议熟记。
| 过程 | 每阶段选择数 | 阶段数 | 结果总数 | 数值示例 |
|---|---|---|---|---|
| 掷硬币 | \(2\) | \(n\) | \(2^n\) | \(n=10\)：\(1024\) |
| 掷骰子 | \(6\) | \(n\) | \(6^n\) | \(n=3\)：\(216\) |
| 数字编号 | \(10\) | \(n\) | \(10^n\) | \(n=6\)：\(1\,000\,000\) |
4. 适用条件：何时不能直接相乘
乘法原理的前提——"无论前面的结果如何，本阶段都恰有 \(n_i\) 种选择"——在使用时必须逐阶段核实。一旦某一阶段的选择数依赖于前面的具体结果，直接相乘就会出错。
考察如下过程：从集合 \(\{1,2,3\}\) 中先取一个数 \(a\)，再取一个严格大于 \(a\) 的数 \(b\)。第一阶段确有 3 种结果，但第二阶段的选择数随 \(a\) 而定：\(a=1\) 时有 2 种，\(a=2\) 时有 1 种，\(a=3\) 时有 0 种。正确的做法是按第一阶段的结果分类相加：总数为 \(2+1+0=3\)，而不是 \(3\times 2=6\)。
这提示我们处理计数问题的通用策略：先问过程能否分成互相独立的阶段——能，则分步相乘；不能，则先按情形分类，对每一类分别使用乘法原理，再把各类数目相加。"分类相加、分步相乘"这八个字将贯穿整个第 1 章，也是第 3 章全概率公式的计数版雏形。
误区一：见到"先后两步"就机械相乘。应先检查第二阶段的选择数是否真的与第一阶段无关；若有关，改用分类相加（如上文 \(\{1,2,3\}\) 的例子）。
误区二：以为"不放回"就不能用乘法原理。从 \(n\) 个不同对象中依次不放回地选取时，可选对象确实越来越少，但第 \(i\) 次选取前剩下的对象数目只依赖阶段编号 \(i\)（恰为 \(n-i+1\) 个），而不依赖之前究竟取走了哪些对象——乘法原理依然适用。这正是 1.3 节排列数公式 \(n(n-1)\cdots(n-k+1)\) 的来源。
5. 本节小结
- 计数基本原理：两阶段各有 \(n_1\)、\(n_2\) 种结果（后者与前者结果无关），则共有 \(n_1 n_2\) 种；\(k\) 个阶段推广为连乘 \(n_1 n_2\cdots n_k\)（定理 1，归纳证明）。
- 成立条件：每一阶段的选择数必须不依赖于前面的具体结果；否则需按第一阶段的结果分类相加。
- 树形图：分层对应分阶段，叶子与完整结果一一对应，叶子总数即结果总数；既是枚举工具，也是检验手段。
- 典型模型：单次 \(m\) 种结果的试验独立重复 \(n\) 次，共 \(m^n\) 种——硬币 \(2^n\)、骰子 \(6^n\)、数字串 \(10^n\)。
- 本节原理是 1.3 排列、1.4 组合与第 2 章古典概率计算的共同起点。
练习
练习 1-2-1
某系统密码长 8 位，每位字符可以是大写字母、小写字母或数字（共 \(26+26+10=62\) 个字符），允许重复。(a) 共有多少个不同密码？(b) 若规定首位必须是数字，又有多少个？
答案与提示(a) 8 个阶段、每阶段 62 种且互不影响，共 \(62^8 = 218\,340\,105\,584\,896 \approx 2.18\times 10^{14}\)。(b) 首位仅 10 种，其余 7 位仍各 62 种，共 \(10\times 62^7 = 35\,216\,146\,062\,080 \approx 3.52\times 10^{13}\)。注意"某一位受限"只改变该阶段的选择数，其余阶段照旧连乘。
练习 1-2-2
连续掷 4 枚硬币，每枚的结果记为"正"或"反"。(a) 所有可能的结果序列共有多少种？(b) 连续掷 \(n\) 枚呢？(c) 其中前两枚都是正面的序列有多少种？
答案与提示(a) 每枚 2 种、互不影响，\(2^4=16\)。(b) 一般地为 \(2^n\)。(c) 前两枚固定为正面（各 1 种），其余 \(n-2\) 枚各 2 种，故 \(1\times 1\times 2^{\,n-2}=2^{\,n-2}\)；当 \(n=4\) 时为 4 种。"固定某些位置"等价于把这些阶段的选择数取为 1，乘法原理照常适用。
练习 1-2-3
从集合 \(\{1,2,3,4\}\) 中先后取两个不同的数 \(a\)、\(b\)，要求 \(b>a\)。有人算得 \(4\times 3=12\) 种。这个乘法用得对吗？请指出违反了乘法原理的哪个条件，并给出正确答案。
答案与提示不对。第二阶段的选择数依赖第一阶段的结果：\(a=1\) 时 \(b\) 有 3 种，\(a=2\) 时 2 种，\(a=3\) 时 1 种，\(a=4\) 时 0 种——"无论第一阶段结果如何都恰有 \(n_2\) 种"这一条件被破坏。应分类相加：\(3+2+1+0=6\) 种。（附带一提：这 6 种恰是无序数对 \(\{a,b\}\) 的个数，1.4 节将给出其一般公式 \(\binom{4}{2}\)。）