广义容斥原理及其应用ppt课件_第1页
广义容斥原理及其应用ppt课件_第2页
广义容斥原理及其应用ppt课件_第3页
广义容斥原理及其应用ppt课件_第4页
广义容斥原理及其应用ppt课件_第5页
已阅读5页，还剩8页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

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

2、数Y？”，“只借一本书的人数Z？” Y= 同理：记 Y1= Y2= Z=Y+Y1+Y2,4,容斥原理与广义容斥原理,5,广义容斥原理,设有与性质,2,n相关的元素N个，Ai为有第 i 种性质的元素的集合.i=1,2,n 定义a(0)=n；当m1时 b(m)是正好具有m个性质的元素的个数。,6,例如，对于n=3,m=2 利用这些记号 b(1)=a(1)-2a(2)+3a(3) b(2)=a(2)-3a(3),广义容斥原理,7,广义容斥原理,定理（广义容斥原理）： 推论：当m=0时,8,广义容斥原理一个应用,在组合数学，Stirling数可指两类数，都是由18世纪数学家James Stirling

3、提出的。 第一类Stirling数是有正负的，其绝对值是n个元素的项目分作k个环排列的方法数目S(n,k)。换个较生活化的说法，就是有n个人分成k组，每组内再按特定顺序围圈的分组方法的数目。 第二类Stirling数是n个元素的集定义k个等价类的方法数目S(n,k)。换个较生活化的说法，就是有n个人分成k组的分组方法的数目。,第二类Stirling数的展开式,s(4,2)=11,9,第二类Stirling数的展开式,n个有区别的球放到m个相同的盒子中（nm），要求无一空盒，其不同的方案数用S(n,m)表示，称为第二类Stirling数。即S(n,m)也就是将n个数拆分成非空的m个部分的方案数。,10,Ai表示第i个盒为空,其它盒任意的方案数（i=1,2,m）。考虑n个有标志的球，放进m个有区别的盒子，得到无一空盒的方案数为,第二类Stirling数的展开式,11,第二类Stirling数的展开式,1

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论