一般网站后台都是哪里做,汕尾网站设计,西安网站建设瑞信,wordpress 微信缩略图容斥原理---概念介绍 容斥原理是一种基本的计数工具。
假设我们有N个对象的集合A#xff0c;设a1, a2,…, ar是这些对象可能有的性质的集合#xff0c;设N(ai )是有性质ai的对象数目。一个对象可能有若干个所讨论的性质#xff08;或一个性质也没有#xff09;。设N(a’i …容斥原理---概念介绍 容斥原理是一种基本的计数工具。
假设我们有N个对象的集合A设a1, a2,…, ar是这些对象可能有的性质的集合设N(ai )是有性质ai的对象数目。一个对象可能有若干个所讨论的性质或一个性质也没有。设N(a’i )计数没有性质ai的对象数目。这时我们有
N N( ai ) N( a’i).
因为一个对象可能有多个性质所以计数既有性质ai又有性质aj的对象数目很有用。这一数目记为N(ai aj). 既没有性质a 又没有性质a 的对象数目记为N(a’i a’j)有性质aj 但是没有性质ai的对象数目记为N(a’iaj )。 我们为N(a’1 a’2 a’3 )开发容斥原理这是既没有性质a1又没有性质a2也没有性质a3的对象数目。这一原理的解释参见下面的韦恩图 首先我们使A包容所有的对象数目总共为N然后我们排除那些有性质a1的所有对象有性质a2的所有对象有性质a3的所有对象。因为某些对象可能有多个性质所有我们有必要加回被过多排斥掉的对象我们加回包容有两个性质的对象这些对象对应于上图的粉红、黄色、绿色区域这时我们又多加回了若干对象即有三个性质的那些对象这些对象对应于上图中深红色区域这些对象必须被排除。 对这一推理的结果加以公式化我们得到下面的公式
N(a’1a’2 a’3) N – N(a1) - N(a1)- N(a1) N(a1 a2) N(a1 a3) N(a2 a3) -N(a1 a2 a3)
一般的没有任意r个性质的对象数量都可以通过扩展上面公式得到。这一公式称为容斥原理principleof inclusion and exclusion。 定理容斥原理
如果N是集合A中的对象的数量集合A中没有性质a1,a2, …, ar 的对象数量由下式给出:
N(a’1a’2...a’r) N – ΣiN(ai) Σi ! jN(ai aj) -Σi,j,k互不相同N(aiajak) (-1)rN(a1a2…ar)
上式中第一个和是对所有取自{1,2,..,r}的i求和第二个和是对所有无序对{i,j}求和其中i和j取自{1,2,..,r}i!j。第三个和是对于无序三元组{i ,j,k}求和其中i ,j,k取自12..ri ,j,k互不相同。一般项是(-1)t乘以形如N(a1 ,a2 ,…,ar )的项的和其中这种形式的和是对于所有无序t元组{i1 ,i2 ,…,it}求和而i1 ,i2 ,…,it取自12..r且i1 ,i2 ,…,it互不相同。 全部选自《应用组合数学(Applied Combinatorics)》原书第二版Fred S.Roberts Barry Tesman著冯速 译
原书第七章
