广义容斥原理及其应用.ppt

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

1、广义容斥原理及其应用主讲人：09013408黄颖第11组小组成员：09013302蔡萌09013304景昕蕊09013406周宇池例：院系图书借记表统计了一个月内《组合数学》、《西游记》、《算法导论》三本书的借记统计情况，借这三本书的人数分别是62、45、33，同时借了《组合数学》、《西游记》的有23人，同时借了《组合数学》、《算法导论》的有18人，同时借了《西游记》、《算法导论》的有10人，同时借了三本书的有3人。问：本月借了这三本书的共有多少人？文氏图简单解决问题A:借《组合数学》B:借《西游记》C:借《算法导论》同时借这三本书的人数设为

2、MM=

3、A∩B∩C

4、A24B15C8203157若将问题修改成“只借《组合数学》的人数Y？”，“只借一本书的人数Z？”Y=同理：记Y1=Y2=Z=Y+Y1+Y2容斥原理与广义容斥原理容斥原理解决的问题：广义容斥原理解决的问题：广义容斥原理设有与性质１,2,···,n相关的元素N个，Ai为有第i种性质的元素的集合.i=1,2,…,n定义a(0)=n；当m>1时b(m)是正好具有m个性质的元素的个数。例如，对于n=3,m=2利用这些记号b(1)=a(1)-2a(2)+3a(3)b(2)=a(2)-3a(3)广义容斥原理广义容斥原理定理（广义容斥原

5、理）：推论：当m=0时广义容斥原理一个应用在组合数学，Stirling数可指两类数，都是由18世纪数学家JamesStirling提出的。第一类Stirling数是有正负的，其绝对值是n个元素的项目分作k个环排列的方法数目S(n,k)。换个较生活化的说法，就是有n个人分成k组，每组内再按特定顺序围圈的分组方法的数目。第二类Stirling数是n个元素的集定义k个等价类的方法数目S(n,k)。换个较生活化的说法，就是有n个人分成k组的分组方法的数目。第二类Stirling数的展开式s(4,2)=11第二类Stirling数的展开式n个有区别的球

6、放到m个相同的盒子中（n>m），要求无一空盒，其不同的方案数用S(n,m)表示，称为第二类Stirling数。即S(n,m)也就是将n个数拆分成非空的m个部分的方案数。Ai表示第i个盒为空,其它盒任意的方案数（i=1,2,…,m）。考虑n个有标志的球，放进m个有区别的盒子，得到无一空盒的方案数为第二类Stirling数的展开式…………第二类Stirling数的展开式n个有标志的球，放进m个无区别的盒子，无一空盒的方案数为：第二类Stirling数的展开式