容斥原理（英文名：Principle of inclusion-exclusion ）又称排容原理， 是组合数学中的核心计数方法，用于计算多个有限集合的并集大小。其核心思想是：一些元素会同时存在于多个集合中，如果仅将这些集合的元素数量相加来求并集中元素数量会导致重复计算，因此需要通过交替加减各集合的交集来消除重复计数，从而精确求得并集的元素数量。
容斥原理的最早运用可追溯至16世纪，当时 瑞士 数学家尼古拉·贝努利在解决错位排列问题时首次采用了这一原理。然而，那时尚未有明确的数学表述。17世纪，数学家John Venn以集合的形式提出了容斥原理的初步数学表达。随后，著名数学家康托尔在17世纪末引入 集合论 ，将容斥原理建立在更为坚实的基础上，使其成为处理复杂计数和概率问题的重要工具。到了19世纪，英国数学家詹姆斯·约瑟夫·西尔维斯特首次提出了该定理的现代表述。
容斥原理的证明可以采用 数学归纳法 或枚举法，将定理进行推广，可得到一些新的结论。 容斥原理广泛地应用于数学、 概率论 、 计算机 等领域，如，在图论中，容斥原理可以用于计算满足某些性质的图的数量，或者计算不满足某些性质的图的数量。
简史
16世纪至17世纪
容斥原理被发掘出来的起因是组合学的——错位排问题，16世纪， 瑞士 数学家尼古拉·贝努利(Nicholas Bernoulli）在解决错位排问题时，用到了容斥原理，但他那时并没有明确的整理和提出容斥原理的数学形式。法国数学家棣莫弗在1718年的著作《机会的学说》（The Doctrine of Chances）中首次明确阐述了容斥原理的思想，并用这个思想解决了一些问题。
18世纪至20世纪
18世纪至20世纪，容斥 定理 在数学领域得到了进一步的发展和推广。著名的数学家 格奥尔格·康托尔 引入了 集合论 ，以此为基础，容斥原理的表述形式得到确定，而随着数学家 莱昂哈德·欧拉 等人对容斥定理进行了深入的研究和推广，提出了更加广泛和深刻的应用。他们在 组合数学 、 概率论 和 数论 等领域中广泛应用容斥定理，推动了容斥定理的发展和应用。在19世纪中叶，柯西、西尔维斯特等数学家严格表述了容斥原理的一般形式，并将容斥原理的思想推广到数论等其他领域的研究中去，推动了容斥原理的应用。随着数学的发展，容斥定理逐渐成为组合数学和概率论等领域的重要工具，为解决复杂的 计数 和概率问题提供了重要的方法和思路。
21世纪
21世纪以来，容斥 定理 在 计算机科学 、 统计学 和 机器学习 等领域得到了广泛的应用。随着 大数据 和 人工智能 等技术的快速发展，容斥定理在处理复杂的计数和概率问题上发挥了重要作用。许多新的领域和学科开始将容斥定理引入到他们的研究和应用中，推动了容斥定理在现代科学和技术领域的发展和应用。
定义
集合形式
在计数时，为了使 重叠 部分不被重复计算，所以先不考虑重叠的情况，把具有某种特征的所有对象的数目，优先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，简化了计数方法，这种计数的方法称为 容斥原理 。
容斥原理运用的最简单的情况是：
问题：求 有限集合 A，B的并的元素数目
这样就会形成两个等式：
等式1：
等式2：
当在涉及到多个集合时，可用最简单的 容斥原理 推出以下的一般情况：
设 是 有限集合 则会形成以下等式
群形式
在 组合计数 中，有一类问题需要计算集合 S 中不符合某些性质（或限制条件）的元素数量。通常情况下，集合 S 中符合某些性质的元素数量很容易计算出来。 容斥原理 是解决这类 计数 问题的有力工具，它提供了一个公式，可以用符合某些性质的元素数量来表示不符合这些性质的元素数量。 首先利用自由 尼尔斯·阿贝尔 群 可以把容斥原理的计数公式表述为 中的2个元素 相等 ，然后设 S 是一个有限集， 是 S 的 子集 （或 S 的分别具有第 个性质的元素组成的子集，当 ，对于任意 即 S 中恰好属于下标在J中的那些子集 的元素所成的子集。| |通常就是所要求计算的对象，在自由 尼尔斯·阿贝尔 群 中 ，直接利用 到Z的 同态 θ可得到经典的 容斥原理 的 计数 公式： 。
相关定理
德摩根定理
德·摩根 定理也称 德摩根 定律、反演法，是由19世纪 英国 著名数学家De Morgan（德·摩根）提出。 德摩根定律是数学运算的基本定律之一，它在数学中的 集合论 、 命题逻辑 、 代数 等领域都有使用，其中在集合中运用时，容斥原理可以配合德摩根定律解答一些相应的难题。 德摩根定理的数学形式为：
(1)
(2)
例题： 设爱好体育的同学组成的集合为 ，爱好文艺的同学组成的集合为 ，整个班级的同学组成的集合是 ，则体育和文艺都爱好的同学组成的集合是 ，体育和文艺都不爱好的同学组成的集合是 ，从而利用 容斥原理 再结合德摩根定律可得：
证明方法
数学归纳法
容斥原理的一般情况，可以通过一种 数学证明 方法—— 数学归纳法 （Mathematical Induction, MI）进行证明。这种方法通常被用于证明某个给定命题在整个（或者局部） 自然数 范围内成立。
已知 时，得到
假设 时有：
所以
但 。
所以可以得到：
。
由上述公式可得：
。
枚举法
枚举法又称元素法，是通过将问题的所有可能的答案一一列举，然后根据条件判断此答案是否合适，合适就保留，不合适就丢弃。根据 容斥原理 的一般基本公式定义可以知道， 的数值等于 有限集合 中所有元素的个数。因此我们可以逐个分析容斥 定理 等式左边集合中所有元素个数与等式右边集合中所有元素个数的关系，在讨论出所有的情况后，再全部进行证明即可得到相应的证明，证明如下：
对于任意一个元素x，分别分析这个元素与等式左边和右边集合的关系。对于容斥原理式子左边有限集 ，元素x要么包含于 要么不包含 ，当元素不包含于 这个元素x也不包含于右边所有的集合，故可知当核算这个元素x的个数时，等式两边成立，都为零。
当这个元素 包含于 ，可假设 有限集合 的等价集合 。然后分析元素x与集合 之间的关系。可知集合中 的所有元素可分类为成如下的各个部分，对于任意给定的一个元素 ：元素x只包含于一个 中，元素x只包含于两个 中，元素x只包含于三个 中，元素x只包含于n个 中。
下面进行逐个证明：
当元素 只包含于一个 中，可假设元素 只包含于 ，由于元素 与集合 的选取具有 任意性 ，其他的证明方法可以类似。因为元素 只包含于中，故 ， 根据集合 交集 的定义，可知当核算这个元素 的个数时，左边式子等于1，右边式子也等于1。
当元素x只包含于两个 中，可假设元素 包含于集合 , ,由于元素 与集合 , 的选取具有 任意性 ，其他的证明方法可以类似。因为元素 只包含于 , 中，故 , ， 根据集合 交集 的定义，可知当核算这个元素 的个数时，左边式子等于1，右边 ， ，
,以此类推，即右边式子的数值等于2 − 1 = 1等于左边，即可证明。
推广
定理一
集合S中恰好具有性质 中k种性质的元素个数为：
推论1：当k=0时，有
以 表示集合S中同时具有性质 的元素个数，则
定理二
设集合 中的元素具有性质 ，且 那么，S种恰好具有 中 个性质 中 个性质的所有元素的权和：
推论2：当集合 中恰好具有 中 个性质 中 个性质的元素的个数为：
。
定理三
设集合 中的元素具有性质 且 ，那么 中恰好具有 中r个性质且至少具有性质 中 个性质的元素的个数，则
证明过程：
任取 ，设满足 中 个性质且满足 中 个性质。为证明等式成立，只需说明
在等式两边被 计数 的次数是相同的即可。
1） 时， 在左边 中未被计数 ，而在等式右边因为 ，故 在等式右边各项的 中，均为被计数。
2） 时，若 时 在左边未被计数 ，在右边也未被计数；若 ，在 左边 )中被计数一次，而在右边仅被 的项 计数一次。
3） 时， 在左边 中未被 计数 ，若 ， 在右边也未被计数，若 ， 仅在 的项中被计数，由此可知， 在 中被计数 次，故 在等式右边所 计数 的总次数是：
类似理论
组合学中还有很多与容斥原理类似的基本原理，如 抽屉原理 、 二项式定理 等，在解决 计数 问题中应用很广泛。
抽屉原理
抽屉原理 (boxprinciple) , 也称做“ 鸽笼原理 ”, 学名 为 狄利克雷 (Dirichlet1805~1859 年 , 德国 数学家 ) 原理 ,是一个基本的、重要的组合学原理。抽屉原理的基础形式：将 个物品放入 个抽屉，则至少有一个抽屉中的物品数不少于两个。
抽屉原理 的其他形式：把 个元素分为 个集合 用 表示这 个集合里相应的元素，则可用 反证法 证明至少存在某个 大于或等于 。
二项式定理
二项式定理，又称 牛顿 二项式定理，是由 英国 物理学家牛顿，在1664年提出后，经过多个世纪的发展，被应用于数学领域多方面，如 方程 、函数、 圆锥曲线 、空间几何、 导数 等。
二项式 定理公式：
其中等式的右边的 多项式 叫做 的 二项式 展开式，展开式有 项，而 叫做二项式的第 项，也称作通项，可以用 来表示，即 叫做二项展开式第 项的 二项式系数 。
应用领域
数学方面
容斥原理 是数学中 计数 方面的一个重要原理，在数学中，容斥原理被广泛应用于 组合计数 问题。这包括排列组合、 集合论 、 图论 等领域。容斥原理通常用于计算满足某些条件的对象数量，以及计算不满足某些条件的对象数量。
素数
素数是 数论 中常被讨论的一种特殊数字，它的个数也是无穷的，但是当在给定的一个数以内分布着多少个素数，并且怎么找到范围内所有的素数时，便可以通过容斥原理来解决在计数时，可能会重复或者漏缺个数的问题。
色多项式
色多项式 是图论中的一个重要概念，用于描述图的染色问题。给定一个图G，其色 多项式 P(G,λ)给出了在用λ种颜色对图G进行染色时所得到的不同染色方案的数量。而在求这个不同染色方案的数量时，便可以引入 容斥原理 来解决重复和漏缺的问题。还可以通过容斥原理来推到出色 多项式 的公式。
概率论方面
概率论（probability theory）又称机率论，是研究 随机性 或不确定性等现象的数学之一，而概率计算问题也可以通过容斥原理来解决。
定理 3：
在 样本空间 的 有限集合 内产生一个结果的实验，事件表示 ，假设样本空间 内的所有结果的几率是均等的，则任何一个事件都不发生的概率为： ，其中 表示事件 发生的概率。
例题：
假设一家快餐店在儿童套餐中放入三种不同的玩具，一份套餐放入一个玩具，而且每一种玩具在任意一份儿童套餐里的几率是均等的，如果买六份儿童套餐，得到所有三种玩具的概率是多少？
解：
此问题等价于把 个可区分的球放入 个可区分的盒子且使得没有为空得概率，所以：
计算机方面
容斥原理算法
在通信网络设计和运行中 可靠度 是一个重要参数，而可靠度可通过找出网络所有的道路、k-树或割集，然后再使用容斥原理的一利用容斥原理中相消项的一个非常简单的性质给出一个求网络可靠度的简单而有效的容斥原理算法，证明了算法恰好给出了容斥原理表达中的不相消项，通过容斥原理的一般公式： 计算出 可靠度 的参数。若记 为 事件的交，则公式可转化为 ，然后再将计算出的道路、k-树或割集带入公式中即可算出可靠度的参数，这就是 容斥原理 算法。
恢复算法
在使用频繁项集时，有时只需要考虑单个项集的情况，例如在 购物篮 分析中，超市经理可能只关心四件产品同时出现的销售情况，而不需要考虑其他产品之间的关系。但有时需要恢复所有频繁项集以进行整体分析，这时就可以根据容斥原理，可以得知项集之间的析取支持度和合取支持度能够相互演算，然后算出单个项集恢复。
超宽带
超宽带是一种新型的无线 通信设备 ，也被称为脉冲 无线电 。这种通讯设备发射出来的脉冲有很多的形式和分类，其中这种脉冲的形式和分类就需要通过 容斥原理 的一般形式，将它们分成不同的集合，然后计算出精确值的问题转化为求满足某些条件的 4 元组的问题，在通过容斥原理的思想，再计算出精确值。