形式陈述

若有限集 $A_1,\ldots,A_m$$A_1,\dots ,A_m$ 两两不交，则

$$ \left|\bigcup_{i=1}^{m}A_i\right|=\sum_{i=1}^{m}|A_i|. $$$$\left|\bigcup _{i=1}^m{A}_i\right|=\sum _{i=1}^m|A_i|.$$

等价地，若一个任务恰好通过若干互斥情形之一完成，而第 $i$$i$ 种情形有 $n_i$$n_i$ 个结果，则总结果数为 $n_1+\cdots+n_m$$n_1+\cdots +n_m$。

直觉

加法原理把对象全集切成互不重叠的类别：每个对象只被一个加数统计，因此不会遗漏，也不会重复。

例子与边界

一个字符若只能是 $26$$26$ 个英文字母之一或 $10$$10$ 个数字之一，共有 $26+10=36$$26+10=36$ 种。若两个类别可能重叠，直接相加会重复计数；此时应先改造成不交划分，或使用容斥原理减去交集。

推论与应用

按首个决策、对象类型或参数范围分类，是组合证明和算法计数的基本策略。乘法原理处理连续阶段，加法原理处理互斥分支，两者结合可计算决策树叶子数。

参考资料

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