欢迎来到天天文库
浏览记录
ID:48085076
大小:280.50 KB
页数:13页
时间:2020-01-12
《广义容斥原理及其应用.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容斥原理与广义容斥原理容斥原理解决的问题:广义容斥原理解决的问题:广义容斥原理设有与性质1,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数的展开式
此文档下载收益归作者所有