乘法原理

把选择过程画成树。第一层有 $n_1$ 个节点，每个节点各生出 $n_2$ 个子节点，第二层便有 $n_1{n}_2$ 个节点；如此逐层继续，叶子数就是乘积。证明只需对层数作数学归纳理路数学归纳法Mathematical induction · Weak induction由基例和从 n 到 n+1 的归纳步推出性质对全部自然数成立。，每一步都对等大的分支使用加法原理理路加法原理Sum rule · Addition principle互斥有限选择类的总数等于各类大小之和。。

选择会相互限制并不自动破坏乘法。安排不同的人担任不同职位时，前面选了谁会改变下一步可选的人，但剩余人数仍固定。真正妨碍直接相乘的是同层不同前缀有不同的延伸数，或不同路径最终表示同一对象。

两位大写字母后接三位数字的编码，允许重复时有 ${26}^2\cdot {10}^3$ 种。若字母部分与数字部分各自禁止重复，则依次有 $26,25,10,9,8$ 个选项，故为 $26\cdot 25\cdot 10\cdot 9\cdot 8$。虽然可用字符取决于之前的选择，每层数量仍然固定。

三件上衣与四条裤子都可自由搭配时有 $3\cdot 4=12$ 套。若第一件上衣只能配两条裤子、另外两件各能配四条，答案变为 $2+4+4=10$，不能继续写 $3\cdot 4$。一般两阶段计数是 $\sum _{a\in A}|B_a|$；只有每个 $|B_a|$ 相同时才化为乘积。

长度 $n\ge 2$ 的二进制串共有 $2^n$ 个。若只要恰含两个 $1$ 的串，逐位自由选择会产生不合法结果；例如长度 $3$ 时，前缀 $11$ 后只允许 $0$，而前缀 $10$ 后只允许 $1$，前缀 $00$ 则已无合法延伸。换一种记录方式，直接选择两个 $1$ 所在的位置，便得到 $(\genfrac{}{}{0ex}{}{n}{2})$ 个结果。

另一个边界是从五人中依次选两人：$5\cdot 4=20$ 数的是有序选择。若结果只是一支两人队伍，每队被数两次，应除以 $2$。这里各层分支数没有问题，问题出在“选择记录到最终对象”的对应不再一一。

逐位安排互异对象得到阶乘理路阶乘Factorial前 n 个正整数的乘积 n!，并约定 0!=1。；分阶段选组、再消除组内顺序得到多项式系数理路多项式系数Multinomial coefficient把 n 个可区分对象分入若干有标号组时的计数系数 n!/(n1!⋯nk!)。。这些除法步骤需要另证每个对象被重复计算的次数相同，不能从乘法原理本身推得。

搜索空间大小也常由各位置选项数给出。若每个合法前缀后都有固定的 $n_i$ 个选项，并在第 $i$ 步条件均匀地选其中一个，那么每条完整记录的概率才都等于 $\prod _{i}1/n_i$。如果各分支延伸数不同，逐层均匀选择一般不会均匀抽到叶子：先等概率选上衣、再等概率选可搭裤子时，两套搭配的上衣对应每套概率 $1/6$，四套搭配的上衣对应每套概率 $1/12$。计数与抽样分布需要分别检查。