容斥问题公式,详细解释一下3个以上的容斥定理

技术容斥问题公式,详细解释一下3个以上的容斥定理这是摩根公式 和 容斥定理 (A交B)的补==(A的补)并(B的补)
(A并B)的补==(A的补)交(B的补)
补==取补集
并==取并集
交==取交集

这就是摩根公式和排除定理。

容斥问题公式,详细解释一下3个以上的容斥定理插图

(A到b的补码)===(A的补码)和(b的补码)。

(甲、乙)的补充=(甲)至(乙)的补充。

补码==取补码集。

并且==取并集。

交叉口==走交叉口。

括号表示顺序。

n(A1A2…Am)=n(Ai)1Im-n(AiAj)1Ijm+n(AiAjAk)-……+(-1)m-1n(A1A2…Am)1I,j,km

注意包含和排除问题的公式:m-1是-1的指数。

这个公式的形式非常复杂。

强调理解。

理解是非常有用的。

你甚至可以不用背就写出自己的公式。

解决问题时你很得心应手。

但是这个公式超出了高中的范围。

高中顶多会讨论m=3的情况。

似乎很难用语言表达。

也就是说,要找到几个集合的并集,可以先把它们全部加起来。

但这样做在某些地方是有意义的。

那么你就得损失一些(公式决定了需要减去什么)。

但是有些地方这种情况会减少。

然后加一些(公式会判断需要加什么)。

……

重复并继续。

最后的结果就是这些集合的并集。

举个例子。

设置a1、a2、a3。

a1={ 1,2,3,4 }

a2={ 2,3,4,5 }

a3={ 3,4,5,1 }

求三个集合的并集。

根据这个公式。

n(Ai)1im=a1 a2 a3={ 1,2,3,4,2,3,4,5,3,4,5,1 }

n(AiAj)1Ijm=(a1a2a3a1)={ 2,3,4 } { 3,4,5 } { 3,4,1}

n(AiAjAk)1Ijm=(a1a2a3)={ 3,4 }

进入公式

三个集合的并集=a1a2a 3(a1a2a3a1)(a1a2a3)={ 1,2,3,4,2,3,4,5,3,4,5,1}。

这是上面公式的具体应用。

我的表达不是很标准。

但是这个公式的方法是这样的。

重新认识百科名片的包含与排除原则。

计数时,包容排除原则必须注意不重复、不遗漏。为了防止重复计算重叠部分,人们开发了一种新的计数方法。这种方法的基本思想是先计算某一内容中包含的所有对象的数量,而不考虑重叠的情况,然后在计数时排除重复计算的数量,这样计算出来的结果既没有遗漏,也没有重复。这种计数方法称为排除原理。

编辑这一段进行详细的推理。

两个集合的可容许性和斥力公式:ab=ab cab(:的重叠部分)三个集合的相容和斥力公式:abc=ab cabbcc。

2.文氏图的方块标记如右图所示:1245构成A,2356构成B,4567构成C 3。等式()的右边指的是下图1 2 3 4 5 6的6个部分:那么ABC还是缺少第7部分。4.方程右侧【 】中的C(4 5 6 7)后,相当于ABC加4563份,减去BC(即562份)后,再加4份。5.从等式右侧的{}中减去CA(即4 ^ 5)后,ABC进一步减5,所以加ABC(即5)正好是AB。

∪C。

编辑本段容斥原理1

如果被计数的事物有A、B两类,那么,A类B类元素个数总和= 属于A类元素个数+ 属于B类元素个数—既是A类又是B类的元素个数。

例1

一次期末考试,某班有15人数学得满分,有12人语文得满分,并且有4人语、数都是满分,那么这个班至少有一门得满分的同学有多少人?

分析

依题意,被计数的事物有语、数得满分两类,“数学得满分”称为“A类元素”,“语文得满分”称为“B类元素”,“语、数都是满分”称为“既是A类又是B类的元素”,“至少有一门得满分的同学”称为“A类和B类元素个数”的总和。

答案

15+12-4=23

试一试

电视台向100人调查前一天收看电视的情况,有62人看过2频道,34人看过8频道,其中11人两个频道都看过。两个频道都没看过的有多少人? 100-(62+34-11)=15

编辑本段容斥原理2

如果被计数的事物有A、B、C三类,那么,A类和B类和C类元素个数总和= A类元素个数+ B类元素个数+C类元素个数—既是A类又是B类的元素个数—既是A类又是C类的元素个数—既是B类又是C类的元素个数+既是A类又是B类而且是C类的元素个数。

例2

某校六(1)班有学生45人,每人在暑假里都参加体育训练队,其中参加足球队的有25人,参加排球队的有22人,参加游泳队的有24人,足球、排球都参加的有12人,足球、游泳都参加的有9人,排球、游泳都参加的有8人,问:三项都参加的有多少人? 分析:参加足球队的人数25人为A类元素,参加排球队人数12人为B类元素,参加游泳队的人数24人为C类元素,既是A类又是B类的为足球排球都参加的12人,既是B类又C类的为足球游泳都参加的9人,既是C类又是A类的为排球游泳都参加的8人,三项都参加的是A类B类C类的总和设为X。注意:这个题说的每人都参加了体育训练队,所以这个班的总人数既为A类B类和C类的总和。 答案:25+22+24-12-9-8+X=45 解得X=3

例3

在1到1000的自然数中,能被3或5整除的数共有多少个?不能被3或5整除的数共有多少个? 分析:显然,这是一个重复计数问题(当然,如果不怕麻烦你可以分别去数3的倍数,5的倍数)。我们可以把“能被3或5整除的数”分别看成A类元素和B类元素,能“同时被3或5整除的数(15的倍数)”就是被重复计算的数,即“既是A类又是B类的元素”。求的是“A类或B类元素个数”。现在我们还不能直接计算,必须先求出所需条件。1000÷3=333……1,能被3整除的数有333个(想一想,这是为什么?)同理,可以求出其他的条件。

例4

分母是1001的最简分数一共有多少个? 分析:这一题实际上就是找分子中不能与1001进行约分的数。由于1001=7×11×13,所以就是找不能被7,11,13整除的数。 解答:1~1001中,有7的倍数1001/7 = 143 (个);有11的倍数1001/11 = 91 (个),有13的倍数1001/13 = 77 (个);有7´11=77的倍数1001/77 = 13 (个),有7´13=91的倍数1001/91 = 11 (个),有11´13=143的倍数1001/43 = 7 (个).有1001的倍数1个. 由容斥原理知:在1~1001中,能被7或11或13整除的数有(143+91+7)-(13+11+7)+1=281(个),从而不能被7、11或13整除的数有1001-281=720(个).也就是说,分母为1001的最简分数有720个.

例5

某个班的全体学生在进行了短跑、游泳、投掷三个项目的测试后,有4名学生在这三个项目上都没有达到优秀,其余每人至少有一项达到了优秀,达到了优秀的这部分学生情况如下表: 短跑 游泳 投掷 短跑、游泳 短跑、投掷 游泳、投掷 短跑、游泳、投掷

1 7 1 8 1 5 6 6 5 2

求这个班的学生共有多少人? 分析:这个班的学生数,应包括达到优秀和没有达到优秀的。 试一试:一个班有42人,参加合唱队的有30人,参加美术组的有25人,有5人什么都没有参加,求两种都参加的有多少人?

例6

在一根长的木棍上有三种刻度线,第一种刻度线将木棍分成10等份,第二种将木棍分成12等份,第三种将木棍分成15等份。如果沿每条刻度线将木棍锯断,木棍总共被锯成多少段?

分析

很显然,要计算木棍被锯成多少段,只需要计算出木棍上共有多少条不同的刻度线,在此基础上加1就是段数了。 若按将木棍分成10等份的刻度线锯开,木棍有9条刻度线。在此木棍上加上将木棍分成12等份的11条刻度线,显然刻度线有重复的,如5/10和6/12都是1/2。同样再加上将木棍分成15等份的刻度线,也是如此。所以,我们应该按容斥原理的方法来解决此问题。用容斥原理的那一个呢?想一想,被计数的事物有那几类?每一类的元素个数是多少? 解答 不计木棍的两个端点,木棍的内部等分点数分别是9,11,14(相应于10,12,15等分),共计34个 由于5,6的最小公倍数为30,所以10与12等份的等分点在30单位处相重,必须从34中减1. 又由于4,5的最小公倍数为20,所以12与15等份的等分点在20单位和40单位两处相重,必须再减去2, 同样,6,4的最小公倍数为12,所以15与10等份的等分点在12,24,36,48单位处相重,必须再减去4 由于这些相重点各不相同.所以从34个内分点中减去1,再减去2,再减去4,得27个刻度点。沿这些刻度点把木棍锯成28段. 容斥原理用于计算集合并集的元素个数,公式为:

n(A1+A2+……+Am)=n(A1)+n(A2)+……+n(Am)-n(A1A2)-n(A1A3)-……-n(A1Am)

-n(A2A3)-n(A2A4)-……-n(A2Am)-……-n(Am-1Am)+n(A1A2A3)+n(A1A2A4)+……

+n(Am-2Am-1Am)-……+(-1)^(m-1)*[n(A1A2……Am)]

注:n(A)表示集合A的元素个数,A+B表示A∪B,AB表示A∩B

内容来源网络,如有侵权,联系删除,本文地址:https://www.230890.com/zhan/49025.html

(0)

相关推荐

  • 数据库中表连接方式有哪些

    技术数据库中表连接方式有哪些这篇文章将为大家详细讲解有关数据库中表连接方式有哪些,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。 1 nested loop

    攻略 2021年11月20日
  • 数据库访问优化法则是什么

    技术数据库访问优化法则是什么本篇文章为大家展示了数据库访问优化法则是什么,内容简明扼要并且容易理解,绝对能使你眼前一亮,通过这篇文章的详细介绍希望你能有所收获。  在网上有很多文章介绍数据库优化知识,但是大部份文章只是对

    攻略 2021年11月23日
  • 美国服务器租用——游戏部署最佳选择USA-IDC

    技术美国服务器租用——游戏部署最佳选择USA-IDC无论您是想增强多人游戏体验还是创造一些额外收入,USA-IDC的美国服务器租用都是运营玩多人游戏(更不用说流内容)的最佳选择。美国服务器提供最高程度的设置控制,并保证有

    礼包 2021年12月24日
  • 抖音粉丝多少钱,抖音真人粉丝多少钱?

    技术抖音粉丝多少钱,抖音真人粉丝多少钱?关于抖音唰赞上热门
    1、其实现在抖音唰赞上热[的确是存在的,但是唰赞上热仅仅只是概率性的,并不是绝对就能够上热门的,所以大家也不需要把所有的希望都寄托于抖音唰赞上热门上。
    2、那么

    测评 2021年10月20日
  • Python实战小项目之如何实现身份证信息校验

    技术Python实战小项目之如何实现身份证信息校验这篇文章主要介绍“Python实战小项目之如何实现身份证信息校验”,在日常操作中,相信很多人在Python实战小项目之如何实现身份证信息校验问题上存在疑惑,小编查阅了各式

    攻略 2021年10月20日
  • leetcode 二叉树分离(数据结构树如何转化为二叉树)

    技术LeetCode如何把二叉搜索树转换为累加树这篇文章主要介绍了LeetCode如何把二叉搜索树转换为累加树,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下

    攻略 2021年12月15日