广义容斥原理及其应用

1、广义容斥原理及其应用主讲人：主讲人： 0901340809013408 黄颖黄颖 第第1111组小组成员：组小组成员： 0901330209013302 蔡萌蔡萌09013304 09013304 景昕蕊景昕蕊 09013406 09013406 周宇池周宇池例：院系图书借记表统计了一个月内组合数学、西游记、院系图书借记表统计了一个月内组合数学、西游记、算法导论三本书的借记统计情况，借这三本书的人数分别算法导论三本书的借记统计情况，借这三本书的人数分别是是6262、4545、3333，同时借了组合数学、西游记的有，同时借了组合数学、西游记的有2323人，人，同时借了组合数学、算法导论的有同时借

2、了组合数学、算法导论的有1818人，同时借了人，同时借了西游记、算法导论的有西游记、算法导论的有1010人，同时借了三本书的有人，同时借了三本书的有3 3人。人。问：本月借了这三本书的共有多少人？问：本月借了这三本书的共有多少人？文氏图简单解决问题A:A:借组合数学借组合数学B:B:借西游记借西游记C:C:借算法导论借算法导论同时借这三本书的人数设为同时借这三本书的人数设为M MM=|AM=|AB BC|C|A 24B15C 8203157若将问题修改成若将问题修改成“只借组合数学的人数只借组合数学的人数Y Y？”，“只借一本只借一本书的人数书的人数Z Z？”Y=Y=同理：记同理：记 Y1=Y

3、1= Y2= Y2= Z=Y+Y1+Y2 Z=Y+Y1+Y2ABCAABACABCABCBBABCABCABCCCACBABC容斥原理与广义容斥原理 容斥原理解容斥原理解 决的问题：决的问题：广义容斥原理解决的问题：广义容斥原理解决的问题：|n21AAA|n_2_1_AAA|n_1_21AAAAAii广义容斥原理设有与性质设有与性质,2,n相关的元素相关的元素N个，个，Ai为有第为有第 i 种性质的元素的种性质的元素的集合集合. .i=1,2,n定义定义a(0)=n；当；当m1时时b( (m) )是正好具有是正好具有m个性质的元素的个数。个性质的元素的个数。12( )miiia mAAA|b(

4、0)n_2_1_AAA|b(m)n121i_AAAAAmmiiii例如，对于例如，对于n=3,=3,m=2=2利用这些记号利用这些记号 b(1)=a(1)-2a(2)+3a(3)b(2)=a(2)-3a(3)121323(2)aAAAAAA212313123(2) bAAAAAAAAA广义容斥原理广义容斥原理定理（广义容斥原理）：定理（广义容斥原理）：推论：当推论：当m=0时时1( )( )(1)( 1)( ) ( 1)( )n mnk mk mmnb ma ma ma nmmka km (0)(0)(1)(2)( 1)( )nbaaaa n 广义容斥原理一个应用在组合数学，Stirling数

5、可指两类数，都是由18世纪数学家James Stirling提出的。第一类Stirling数是有正负的，其绝对值是n个元素的项目分作k个环排列的方法数目S(n,k)。换个较生活化的说法，就是有n个人分成k组，每组内再按特定顺序围圈的分组方法的数目。第二类Stirling数是n个元素的集定义k个等价类的方法数目S(n,k)。换个较生活化的说法，就是有n个人分成k组的分组方法的数目。第二类第二类StirlingStirling数的展开式数的展开式 s(4,2)=11第二类Stirling数的展开式n n个有区别的球放到个有区别的球放到m m个相同的盒子中（个相同的盒子中（nmnm），要求无一空盒，

6、其），要求无一空盒，其不同的方案数用不同的方案数用S(n,m)S(n,m)表示，称为第二类表示，称为第二类StirlingStirling数。即数。即S(n,m)S(n,m)也就是将也就是将n n个数拆分成非空的个数拆分成非空的m m个部分的方案数。个部分的方案数。mknkkmkmCm0)(,() 1(!1m)S(n,Ai表示第i个盒为空,其它盒任意的方案数（i=1,2,m）。考虑考虑n n个有标志的球，放进个有标志的球，放进m m个有区别的盒子，得到无一空盒的方案数为个有区别的盒子，得到无一空盒的方案数为 mA.AA21）mS(n,m! 第二类Stirling数的展开式 miijjiAAa1)2(nm)2(2m miiiiiiiikkkAAAka1112121.)(nkmk)(mmAAAa.)1 (21nm)1(1mnmNa)0(第二类Stirling数的展开式n个有标志的球，放进m个无区别的盒子，无一空盒的方案数为：)(