包容与排斥原则(PIE)

的包容与排斥原则是计算数量的计数技术元素满足多个属性中的至少一个，同时保证满足多个属性的元素不会被计算两次。

派背后的潜在想法是求解满足两个类别中的至少一个的元素数量，并减去重叠防止重叠双重计数．例如，至少养一只猫或至少养一只狗的人数，可以用养猫的人数加上养狗的人数，再减去同时养狗和猫的人数来算出。

PIE在组合和概率解决问题时，必须设计一种计数方法，以确保一个对象不被计算两次。

在物体被分成两部分(可能不相交)的情况下集，包含和排除状态的原则

$| A \ CUP B |= | A | + | B |- | A \ CAP B |，$

在哪里 $|的|$表示基数，或集合的元素数 $年代$in.设定表示法．

要证明此语句，我们将显示属于其中一个集合中的每个元素一次都被计算一次，并且每个未在这些集合中的元素都被计算为零次。

• 案例1.元素不在 $一个$，而不是 $B$．
  很明显，它在LHS中被计数为零。很明显，它在RHS中被计数为零。

• 案例2.元素在 $一个$，而不是 $B$．
  它将在LHS上计数一次。在RHS上，它被计算一次 $| A |$．

• 案例3.元素不在 $一个$，并在 $B$．
  它将在LHS上计数一次。在RHS上，它被计算一次 $B | |$．

• 例4。元素是在 $一个$，在 $B$．
  它将在LHS上计数一次。在RHS上，它被计数 $+1$in. $| A |$， $+1$in. $B | |$和 $-1$in. $|A \cap B$．因此，它被计算一次。

用维恩图可以很容易地描述两组的PIE:

从1到100的整数是2或3的倍数？

---

让我们 $一个$是从1到100的整数集成，这是2的倍数 $\rvert A \rvert = 50$．
让我们 $B$是从1到100的整数集，是3的倍数，那么 $\ ltvert b \ rfter = 33$．
现在, $B \帽$是从1到100的整数集成，它是2和3的倍数，因此是6的倍数，暗示 $(2) (1) (2) (2) (3) (3) (4) (4$．

因此,通过派, $|A \ CUP B |= | A | + | B | - | A \帽B |= 50 + 33 - 16 = 67. \ _ \ Square$

我们已经看过两组的情况。在我们深入研究一般情况之前，让我们考虑有3个集合。

如果有三个集合，则包含和排除原则声明

$|一杯\ B \杯C | = | | + | | B + C | | - | - - - | | \帽B C | - | B \ \帽帽C | + | B \ \帽帽C |。$

我们可以通过考虑事件的Venn图来为自己验证这些陈述：

一所学校里有三种类型的学生:极客、追求者和运动员。每个学生至少被分为其中一个类别。学校的学生总数是1000人。假设给出以下情况:

• 怪人的学生总数是310。
• Wannabees的学生总数是650。
• 学生中运动员的总数是440人。
• 既有极客和崇拜者的学生总数是170。
• 既有极客和运动员的学生总数是150。
• 同时是运动员的学生有180人。

适合所有3个类别的学生总数是多少？

---

让我们 $G, W$分别表示为极客，想成为，和运动员。根据包容和排斥的原则，我们有

$n（g \ cap w \ cap a）= n（g）+ n（w）+ n（a） - n（w \ cap g） - n（g \ cap a） - n（w \ cap a）+n（g \ cap w \ cap a），$

这给了我们 $1000 = 310 + 650 + 440 - 170 - 150 - 180 + n(G\cap W \cap A)=900 + n(G\cap W \cap A)$．

因此，适合所有3个类别的学生总数为100。 $_ \广场$

我们把证明推迟到一般情况下进行。如果您感兴趣，可以复制上面的证明并检查每个元素 $A杯子B杯子C$在RHS上完全算一下。

更一般地，如果 $A_1 A_2 ldots A_n$是有限套，然后是包含和排除状态的原则

$\ displaystyle \ left | \ bigcup_ {i = 1} ^ n a_i \ loct |= \ sum_ {i = 1} ^ n \ lef | a_i \ loct |- \ sum_ {1 \ leq i$

主要文章:紊乱

有八位客人参加了一个秘密的圣诞老人聚会。每位客人都带来一份礼物，而每位客人也会收到另一份礼物作为回报。任何人都不允许收到他们带来的礼物。有多少种分配礼物的方式?

---

让我们 $一个$表示这组方法来分配礼物，使每个人都收到礼物，可能是他们自己的礼物。让我们 $ai$表示分配礼物的方式 $我$收到自己的礼物。然后我们要找到

$|A| - |A_1 \杯A_2 \杯cdots \杯A_8|。$

自从 $ai$是人的一套方式 $我$要收到他/她自己的礼物，给下一个人的礼物有7种选择，给下一个人的礼物有6种选择，以此类推。根据乘积法则，

$| A_I | = 7 \ times 6 \ times \ Cdots \ times 2 \ times 1 = 7！$

自从 $ai \帽A_j$是人的一组人 $我$和人 $j$两人都收到了自己的礼物，下一个人有6个礼物选择，下一个人有5个礼物选择，以此类推。根据乘积法则，

$|A_i∑A_j| = 6 * 5 * cdots * 2 * 1 = 6!$

通过继续这个论点，如果 $k$人们收到自己的礼物，然后就有了 $(公布)!$可能的方式。应用馅饼，我们获得

$|A| - |A_1 \cup A_2 \cup \cdots \cup A_8| = 8!-{8 \选择1}\乘以7!+{8\选择2}\乘以6!- cdots + {8 \choose 8} \乘以1!= 14833。\ _ \广场$

注意:哄骗的 $n$对象是对象的置换，使得其中没有一个都在同一个地方。可以做到这一点的数量是表示为的 $d_n.$，此计算显示 $D_8 = 14833$．

从1到100的所有整数是2或3的倍数的和是多少?

---

虽然馅饼通常用于计算集合的元素，但是如果我们删除了 $| \ cdot |$符号，这句话仍然正确。例如，在两个变量中， $a \ cup b = a + b - a \ cap b$．同样的证明使用维恩图可以证明每个元素包含一次。因此，元素的总和 $一个\杯b$等于元素的和 $一个$加上元素的总和 $B$减去元素的总和 $a \ cap b$．让我们 $一个$是2的倍数 $B$是3的倍数的集合 $B \帽$是6的倍数，因此的总和 $一个\杯b$是

$\压裂{(2 + 100)\乘以50}{2}+ \压裂{(3 + 99)\ * 33}{2}- \压裂{(6 + 96)\乘以16}{2}= 3417。\ _ \广场$

我们有7个球各种颜色（红色，橙色，黄色，绿色，蓝色，靛蓝，紫色）和3个盒子，每种不同的形状（四面体，多维数据集，十二锭）。有多少种方法将这7个球放入3个盒子中，使得每个盒子至少包含1个球？

---

让我们 $X$是在没有限制的情况下，我们分配球的方式的总数。每个球都可以放进三个盒子中的任何一个，所以 $| | = 3 X ^ 7$．让我们 $T$四面体盒子里没有球， $C$多维数据集盒没有球的方式，和 $D$道德向量盒没有球的这种方式。我们想找到

$|X| - |T \cup C \cup D|。$

我们有 $| t | = | c | = | d | = 2^7$，由于球可以放入另外两个盒子中的一个，并且 $| T \ CAP C |= | C \ CAP D |= | D \ CAP T |= 1 ^ 7$，因为所有球必须放在剩下的盒子里，而且 $|T\cap C \cap D = 0$．因此，饼图意味着

$| = 3^7 - 3 * 2^7 + 3 * 1^7 - 0 = 1806。\ _ \广场$