容斥原理及其应用

《容斥原理及其应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第13卷第2期高等函授学报(自然科学版)Vol.13No.22000年4月JournalofHigherCorrespondenceEducation(NaturalSciences)February2000文章编号:1006-7353(2000)02-0017-04X容斥原理及其应用陈敬华(湖北师范学院数学系)摘要:容斥原理是组合计数的一个重要工具。本文对容斥原理的表现形式作了陈述,重点论述了容斥原理在数学各个分支中的应用。关键词:容斥原理;权;可重组合;积和式中图分类号:O157文献标识码:A1引言元素的权和,W(r)=∑W(pi1,pi2,⋯,容斥原理,又称包含排斥原理,是组合数pi

2、r)其中和式取遍P的r元子集,当r=0学中解决计数问题的一个重要工具之一。对时,规定W(0)等于S中所有元素的权的和。初学者而言,无论是在对容斥原理的理解,还令E(k)表示S中正好具有p中k个性质的是在如何运用容斥原理方面,存在着一定的元素的权的和,E(0)表示S中不具有p中任困难,值得我们仔细揣摩体会。何性质的元素的权的和,则有容斥原理的表述形式:k+1E(k)=W(k)-W(k+1)+简单形式:设有限集合S和与S中的元k素有关的性质集P={p1,p2,⋯,pm},令Aik+2m-kmW(k+2)-⋯+(-1)W(m)={x

3、x∈S,且x具有性质pi},Ai=S-kkAi(i=1,2,⋯

4、,m),则③mE(0)=W(0)-W(1)+W(2)-⋯+

5、A1∪A2∪⋯∪Am

6、=∑

7、Ai

8、-(-1)mW(m)④i=1容斥原理的证明详见有关文献,对于容∑

9、Ai∩Aj

10、+∑

11、Ai∩Aj∩Ak1≤i

12、-⋯+(-1)

13、A1∩A2∩⋯∩Am

14、①(1)①式②式比较直观,其中①式是加m

15、A1∩A2∩⋯∩Am

16、=

17、S

18、-∑

19、Ai

20、+法法则的推广。又由集合论知:

21、S

22、=

23、A1∪i=1A2∪⋯∪Am

24、+

25、A1∪A2∪⋯∪Am

26、∑

27、Ai∩Aj

28、-∑

29、Ai∩Aj∩Ak

30、+1≤i

31、A1∪A2∪⋯∪Am

32、+

33、A1∩A2∩⋯∩m⋯+

34、(-1)

35、A1∩A2∩⋯∩Am

36、②Am

37、,因此①式和②式反映的是同一个问题一般形式:设S,P同上,F为一域,对每的两个方面。若已知其中一面,则另一面也就个a∈S,有唯一ω(a)∈F与a对应,称得到。ω(a)为a的权,W(pi1,pi2,⋯,pir)为S中(2)④式是③式当k=0时的特殊情同时具有这r个性质pi1,pi2,⋯,pir的所有形,若对S的任何元素a,w(a)=1,则④式X收稿日期:2000-02-1617第13卷第2期高等函授学报(自然科学版)Vol.13No.22000年4月JournalofHigherCorrespondenceEducation(NaturalScienc

38、es)February2000就是②式,初学者对①～④式之间的关系一般地,对任意整数k,1≤k≤n,有往往理解不够,它们之间的关系见下图:

39、Ai∩Ai∩⋯∩Ai

40、=(n-k)!,其中12kk=0w(a)=1③式④式②式①式{i1,i2,⋯,ik}是{1,2,⋯,n}的一个k—组(3)W(r)=∑W(pi1,pi2,⋯,pir)求合。和是对P的所有r-子集来求,即表示S中由容斥原理得:至少具有P中r个性质的元素的权的和。nnDn=n!-(n-1)!+(n-2)!-⋯+(4)若所求解问题能表示为求

41、A1∩12A2∩⋯∩Am

42、(即求某集合S中不满足某nn(-1)0!些条件的元素的个数或能表示为求

43、其集合中n11n1不满足某些条件的元素的权的和)时,通常=n!1-+-⋯+(-1).1!2!n!可考虑使用容斥原理。2.2多重集的r—可重组合数N对于什么样的问题可使用容斥原理,以设有多重集W={n1·a1,n2·a2,⋯,nk·及如何使用容斥原理,下面我们从几个方面ak},n1+n2+⋯+nk=n.对r

44、·c}的10—可重组合数。j(j=1,2,⋯,n)。试求Z的所有错位排列的分析表面看来,同例1相比,似乎此个数Dn。问题与使用容斥原理联系不大,但仔细分析,分析由题设,Z的所有错位排列所构会觉得有使用容斥原理的可能性。碰到此类成的集合是Z的全排列集中去掉满足条件ij问题大家容易得到的是多重集T={∞·a,=j的全排列余下的全排列所构成的,可使∞·b,∞·c}的10—可重组合数N=用容斥原理。3+10-112解用S表示Z的