包容与排斥原则(PIE)
两套
在物体被分成两部分(可能不相交)的情况下集包括和排除原则的国家
为了证明这个语句,我们将证明,属于这些集合中的每一个元素都被精确计数一次,而不属于这些集合的每一个元素被精确计数零次。
案例1。元素不在 ,而不在 .
很明显,它在LHS中被计数为零。很明显,它在RHS中被计数为零。例2。元素是在 ,而不在 .
它将在LHS上计数一次。在RHS中,它被计算一次 .例3。元素不在 ,并在 .
它将在LHS上计数一次。在RHS中,它被计算一次 .例4。元素是在 ,在 .
它将在LHS上计数一次。在RHS上,它被计数 在 , 在 和 在 .因此,它被精确地计算一次。
用维恩图可以很容易地描述两组的PIE:
从1到100有多少整数是2或3的倍数?
让 从1到100是2的倍数的整数集合,那么 .
让 是从1到100的整数集,是3的倍数,那么 .
现在, 从1到100的整数集是2和3的倍数,因此是6的倍数,意味着什么 .因此,通过派,
三组及以上
我们已经看过两组的情况。在我们深入研究一般情况之前,让我们考虑有3个集合。
如果有三个集合,则包含和排除原则声明
我们可以通过考虑事件的维恩图来验证这些说法:
一所学校里有三种类型的学生:极客、追求者和运动员。每个学生至少被分为其中一个类别。学校的学生总数是1000人。假设给出以下情况:
- “极客”学生总数为310人。
- 学生的总数是650人。
- 学生中运动员的总数是440人。
- 同时是“极客”和“想成为”的学生共有170人。
- 同时是“极客”和“运动员”的学生共有150人。
- 同时是运动员的学生有180人。
符合这三种情况的学生总数是多少?
让 分别表示为极客,想成为,和运动员。根据包容和排斥的原则,我们有
这给了我们 .
所以符合这三个类别的学生总数是100人。
我们把证明推迟到一般情况下进行。如果您感兴趣,可以复制上面的证明并检查每个元素 在RHS上只计算一次。
更一般的,如果 那么有限集是包含和排除的状态吗
紊乱
主要文章:紊乱
有八位客人参加了一个秘密的圣诞老人聚会。每位客人都带来一份礼物,而每位客人也会收到另一份礼物作为回报。任何人都不允许收到他们带来的礼物。有多少种分配礼物的方式?
让 表示一套分配礼物的方法,以便每个人都能收到一份礼物,可能是他们自己的。让 表示一套分发礼物的方式 收到自己的礼物。然后我们要找到
自 是人的一套方式吗 要收到他/她自己的礼物,给下一个人的礼物有7种选择,给下一个人的礼物有6种选择,以此类推。根据乘积法则,
自 是人的一套方式吗 和人 两人都收到了自己的礼物,下一个人有6个礼物选择,下一个人有5个礼物选择,以此类推。根据乘积法则,
通过继续这个论证,如果 人们收到自己的礼物,然后就有了 可能的方法。应用PIE,我们得到
注意:精神错乱的 物体是物体的排列,没有一个物体停留在相同的地方。可以做到这一点的方法的数量被表示出来 ,计算结果表明 .
解决问题
从1到100的所有整数是2或3的倍数的和是多少?
虽然PIE通常用于计数集合中的元素,但如果我们删除 符号,这句话仍然正确。例如,在两个变量中, .同样的证明使用维恩图可以证明每个元素包含一次。因此,元素的总和 等于元素的和 加上元素的和 减去元素的和 .让 是2和的倍数的集合 是3的倍数的集合 是6的倍数的集合,因此是和 是
我们有7个不同颜色的球(红、橙、黄、绿、蓝、靛、紫)和3个不同形状的盒子(四面体、立方体、十二面体)。有多少种方法将这7个球放入3个盒子中使每个盒子中至少有一个球?
让 是在没有限制的情况下,我们分配球的方式的总数。每个球都可以放进三个盒子中的任何一个,所以 .让 四面体盒子里没有球, 立方体盒子没有球的一组方法 使十二面体盒子没有球的一系列方法。我们想找到
我们有 ,因为这些球可以放在另外两个盒子中的一个 ,因为所有的球必须放在剩下的盒子里,并且 .因此,派意味着