广义容斥原理及其应用

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,广义容斥原理及其应用,主讲人：,09013408,黄颖,第11组小组成员：,09013302,蔡萌,09013304,景昕蕊,09013406,周宇池,例：,院系图书借记表统计了一个月内组合数学、西游记、算法导论三本书的借记统计情况，借这三本书的人数分别是62、45、33，同时借了组合数学、西游记的有23人，同时借了组合数学、算法导论的有18人，同时借了西游记、算法导论的有10人，同时借了三本书的有3人。,问：本月借了这三本书的共有多少人？,文氏图简单解决问题,A:借组合数学,B:借西游记,C:借算法导论,同时借这三本书的人数设为M,M=|A,B,C|,A,24,B,15,C,8,20,3,15,7,若将问题修改成“只借组合数学的人数Y？”，“只借一本书的人数Z？”,Y=,同理：记,Y1=,Y2=,Z=Y+Y1+Y2,容斥原理与广义容斥原理,容斥原理解,决的问题：,广义容斥原理解决的问题：,广义容斥原理,设有与性质,2,n,相关的元素,N,个，,A,i,为有第,i,种性质的元素的集合.,i,=1,2,n,定义a(0)=n；当m1时,b,(,m,)是正好具有,m,个性质的元素的个数。,例如，对于,n,=3,m,=2,利用这些记号,b,(1)=,a,(1)-2,a,(2)+3,a,(3),b,(2)=,a,(2)-3,a,(3),广义容斥原理,广义容斥原理,定理（广义容斥原理）：,推论：当,m,=0时,广义容斥原理一个应用,在组合数学，Stirling数可指两类数，都是由18世纪数学家James Stirling提出的。,第一类Stirling数是有正负的，其绝对值是n个元素的项目分作k个环排列的方法数目S(n,k)。换个较生活化的说法，就是有n个人分成k组，每组内再按特定顺序围圈的分组方法的数目。,第二类Stirling数是n个元素的集定义k个等价类的方法数目S(n,k)。换个较生活化的说法，就是有n个人分成k组的分组方法的数目。,第二类,Stirling,数的展开式,s(4,2)=11,第二类Stirling数的展开式,n个有区别的球放到m个相同的盒子中（nm），要求无一空盒，其不同的方案数用S(n,m)表示，称为第二类Stirling数。即S(n,m)也就是将n个数拆分成非空的m个部分的方案数。,A,i,表示第i个盒为空,其它盒任意的方案数（i=1,2,m）。,考虑n个有标志的球，放进m个有区别的盒子，得到无一空盒的方案数为,第二类Stirling数的展开式,第二类Stirling数的展开式,n,个有标志的球，放进,m,个无区别的盒子，无一空盒的方案数为：,第二类Stirling数的展开式,