容忍和排斥原则的适用

不相容原理的分类是什么？

不相容原理的分类是什么？

与容斥原理相关的数学知识如下图所示:

其中，宽容原则可以分为:

初等容斥原理:二元、三元情况下的第一个公式(中小学数学涉及的内容)；

经典的容斥原理:第一个公式推广到任意有限多元，增加第二个公式；

宽容与排斥的广义原理:扩展第二个公式:

下面，对以上几类进行简单介绍:

容忍和排斥的基本原则

关于任意集合a和b，

从上图可以直观的得到:

这是容忍和排斥原则最原始的公式。

注意:在公式(1)中，|A|表示集合A中包含的元素个数，例如|{a，b，c}| = 3。

在实际应用中，公式(1)中集合元素的个数还可以换成图形的面积、几何的体积等。例如:

如下图所示，在桌子上放置一个长方形和一个正方形。求桌面被两个图形覆盖的面积？

解决方案:根据包含和排除原则，有:

两个图形的覆盖面积=矩形面积，正方形面积-三角形面积= 4 × 7 5 × 5-4 × 3/2 = 28 25-6 = 47

公式(1)是包容和排斥的二元原理。在此基础上，通过使用集合交集和并集的分配率:

可以扩展到三进制:

也就是说，

举一个容忍和排斥的三元原理的例子:

小学三门主课:语文、数学、英语、小明的课。7个人喜欢语文，5个人喜欢数学，3个人喜欢英语，3个人既喜欢语文又喜欢数学，2个人既喜欢语文又喜欢英语，2个人既喜欢数学又喜欢英语，还有一个人3门主课都喜欢。问问有多少人喜欢至少一门主课。①

解法:设A = {喜欢语文}，B = {喜欢数学}，C = {喜欢英语}，那么我们知道:| a | = 7，| b | = 5，| c | = 3，| a ∩ b | = 3，| a ∩ c | |显然，A∪B∪C = {至少喜欢一门主菜的人}。根据容忍和排斥的三元原则，有:

| A∪B∪C | = | A | | B | | C |-| A∪B |-| A∪C |-| B∪C | | A∪B∪C | = 7 5 3-3-2-2 1 = 9

容忍和排斥的经典原则

考虑例子①，知道小明班有20个人，然后问有多少人不喜欢任何一门主菜？

解法:设x = {小明班上的所有人}，因为a、b、c是喜欢语文、数学、英语的人，所以a、b、c是不喜欢语文、数学、英语的人，然后Aᶜ ∩ Bᶜ ∩ Cᶜ是不喜欢任何主课的人。用德·摩根定理:

有:

结合公式(2)，有:

所以，答案是:

上述例子中的公式(3)称为包含和排除原理的第二个公式。它是三进制形式，而二进制形式是:

因此，公式(1)和(2)被称为容斥原理的第一个公式。

以上是两个或三个元素的情况。接下来我们会有一个质的飞跃，把容差和排斥原理推广到任何有限元。

从第一个公式开始，为了找到规则，使用下标来区分集合，然后将公式(2)重写为:

将括号中的单词写成sum:

所以猜一下:对于任何一个集合A，A，...A _ n，满足:

归纳证明:

假设当有集合时上述猜想成立，则有:

等式的左侧是:

所以，有:

这证明了:

则证明公式(5)有效。这是第一个公式的一般形式。

然后，利用德·摩根定理，可以从第一个公式的一般形式推导出第二个公式的一般形式:

容忍和排斥的普遍原则

或者，例①，问:有多少人只喜欢语文？

分析:只喜欢语文的是喜欢语文但不喜欢数学和英语的，也就是A ∩ Bᶜ ∩ Cᶜ

使b' = a ∩ b，c' = a ∩ c，则b' a，c' a，则取a为全集，则(b') = a ∩ b，(c') = a ∩ c，则取a为全集，利用经典的容差原理。

也就是说，

根据上面的分析，答案是| a ∩ b ∩ c | = 7-3-21 = 3。

将例①中的问题升级，问:有多少人恰好喜欢一道主菜？

分析:只喜欢一门主菜的人数=只喜欢语文的人数，只喜欢数学的人数，只喜欢英语的人数。以上(7)是喜欢中文的人数，可以类似得出。只喜欢数学的人数和只喜欢英语的人数分别是:

所以，得到:

更进一步，答案是:

| a∩bᶜ∩cᶜ||aᶜ∩b∩cᶜ||aᶜ∩bᶜ∩c | =(7 5 3)-2×(3 2 2)3×1 = 15-14 3 = 4

如果是，请定义①:

然后，等式(8)可以重写为:

再想想，例①，问:有多少人恰好喜欢第二道主菜？

分析:根据以上经验，有，

然后得到:

所以，答案是:

| a∩b∩cᶜ| | a∩bᶜ∩c ||aᶜ∩b∩c | =(3 2 2)-3×1 = 7-3 = 4

用定义①重写(8’):

此外:

只是喜欢三道主菜的人数=喜欢所有三道主菜的人数，所以:

刚好喜欢零主菜的人数=不喜欢三门主菜的人数。这是第二个公式的三元形式公式(3)，改写为:

比较等式(9)、(9’)、(9”)和(9’’，我们可以很容易地得出结论:

这就是广义的容斥原理。

这里介绍一下容斥原理的分类。最后，需要说明的是:

广义容斥原理实际上是定义在幂集上局部有限偏序集上的Mobius逆变换(又称Mobius反演)的一个特例。所以，莫比乌斯逆变换也可以看作是容斥原理的一种分类。但是真的没有地方介绍莫比乌斯逆变换，只能以后再说了。

由于Mobius逆变换在初等数论中的重要性，许多初等数论问题都可以看作是容斥原理的应用。

由于篇幅同样有限，我没有证明最后一个广义包含原理。这个证明其实一文不值，因为只要证明了莫比乌斯逆变换，广义包含原理自然就被证明了。

由于本人数学水平有限，出现错误在所难免，欢迎各位老师批评指正。)