形式陈述

对有限集 $A_1,\ldots,A_m$$A_1,\dots ,A_m$，有

$$ |A_1\times\cdots\times A_m|=\prod_{i=1}^{m}|A_i|. $$$$|A_1\times \cdots \times A_m|=\prod _{i=1}^m|A_i|.$$

更一般地，若第 $i$$i$ 阶段在每个此前合法选择之后都恰有 $n_i$$n_i$ 种延伸，则完整选择序列共有 $\prod_i n_i$$\prod _i{n}_i$ 种。这里不需要概率意义上的独立性，只要求每层分支数固定。

直觉

每个第一阶段结果都能与全部第二阶段结果配对，再与全部第三阶段结果配对；等规模分支逐层复制，因而总数相乘。

例子与边界

两位字母加三位数字的编码在允许重复时有 $26^2\cdot10^3$${26}^2\cdot {10}^3$ 种。即使禁止重复，只要每层剩余选择数对所有合法前缀都相同，仍可用 $26\cdot25\cdot10\cdot9\cdot8$$26\cdot 25\cdot 10\cdot 9\cdot 8$。若后续选择数依赖具体前缀且不恒定，必须分情形求和。

推论与应用

乘法原理导出排列数、函数数和有限笛卡尔积大小，并用于分析穷举空间、密码长度和多阶段实验。它与加法原理共同构成初等计数的主干。

参考资料

• Eric Lehman, F. Thomson Leighton, and Albert R. Meyer, Mathematics for Computer Science, rev. 2018, §15.3.
• Kenneth H. Rosen, Discrete Mathematics and Its Applications, 8th ed., McGraw-Hill, 2019, §6.1.