加法原理

加法原理（rule of sum或addition principle）是组合计数的基本组合原理。简单而言，若有$A$种方式做某事，又有$B$种方式做另一件事，且恰好要做其中之一，则总共有$A+B$种方案。

严格化的数学中，加法原理是有关集合大小的事实，断言任意有限多个两两互斥的集合大小之和，等于其并集的大小。以符号表示为，若集合$S_{1},S_{2},\ldots ,S_{n}$两两互斥，则有

$|S_{1}|+|S_{2}|+\cdots +|S_{n}|=|S_{1}\cup S_{2}\cup \cdots \cup S_{n}|.$

简单例子

设学校田径运动会中，学生要报名恰好一个项目，可以是田赛或径赛。若选田赛，则可以选跳高、跳远、铅球三项之一。若选径赛，则可以选一百米跑、四百米跑两项之一。

应用加法原理，共有$3+2=5$种报名方案。

容斥原理

主条目：容斥原理

三幅文氏图，每个区域标的数，是该图下方算式中，该区域（对应的集合）的元素数了多少次，验证了容斥原理。

容斥原理可以视为加法原理的推广，因为是同样计算若干个集合之并的大小，但不要求各集合两两互斥。其断言，若$A_{1},A_{2},\ldots ,A_{n}$为有限集，则

${\begin{aligned}{\biggl |}\bigcup _{i=1}^{n}A_{i}{\biggr |}{}=\sum _{i=1}^{n}\left|A_{i}\right|&-\sum _{i,j\,:\,1\leq i<j\leq n}\left|A_{i}\cap A_{j}\right|\\&+\sum _{i,j,k\,:\,1\leq i<j<k\leq n}\left|A_{i}\cap A_{j}\cap A_{k}\right|-\ \cdots \ +\left(-1\right)^{n-1}\left|A_{1}\cap \cdots \cap A_{n}\right|.\end{aligned}}$

参见

• 其他组合技巧如：
  • 乘法原理——组合计数原理，计算从两集合各取一个元素的方法数
  • 容斥原理——组合数学的计数技巧，重复数算的数目要扣除