《4142容斥原理》由会员分享,可在线阅读,更多相关《4142容斥原理(42页珍藏版)》请在金锄头文库上搜索。
1、4.1 n4.1.1 集合的运算n4.1.2 容斥原理简单形式n4.1.3 容斥原理一般形式n4.1.4 Jordan14.1.1 集合的运算n(1)集合A与B的交 ABxxAxBn(2)集合A与B的并 ABxxAxBn(3)集合A与B的差(B相对A的补) ABxxAx Bn(4)集合A的绝对差(补) EA,其中E表示全集 24.1.1 集合的运算n(1)对合律 An(2)幂等律 AAA AAAn(3)交换律 ABBA ABBA34.1.1 集合的运算n(4)结合律 (AB)CA(BC) (AB)CA(BC)n(5)分配律 A(BC)(AB)(AC) A(BC)(AB)(AC)44.1.1 集
2、合的运算n(6)否定律 A A En(7)零律 A AEEn(8)同一律 AEA A A54.1.1 集合的运算n(9)吸收律 A(AB)A A(AB)An(10)德摩根律 64.1.1 集合的运算n|A| 有限集合A的元素个数n a的整数部分n为方便,把AB简记为AB 74.1.1 集合的运算n例例4.1.1计算1600(包括1与600)中不能被6整除的整数个数。 84.1.1 集合的运算n解解 令 E1,2,3,600 Ax|xE且x能被6整除 由于每连续6个整数的第6个整数都能被6整 除,因而|A| 100 从而 |E|A|60010050094.1.2 容斥原理简单形式n定理定理 4.
3、1.1 设A、B、C为有限集,则 (1)|AB|A|B|AB| (2)|ABC|A|B|C|AB|AC| |BC|ABC|104.1.3 容斥原理一般形式n定理定理4.1.2 设A1,A2,An均为有限集,则 |A1A2An| (1)n-1|A1A2An| 114.1.3 容斥原理一般形式n定理定理4.1.3 设A1,A2,An均为有限集,则 |E| (1)n|A1A2An| 124.1.3 容斥原理一般形式n例例4.1.2 求1250之间(包括1和250)能被2或3或5整除的整数的个数。134.1.3 容斥原理一般形式n解解 设 E1,2,250 A1x|xE且x能被2整除 A2x|xE且x
4、能被3整除 A3x|xE且x能被5整除 问题即求 |A1A2A3| 144.1.3 容斥原理一般形式n而|A1| 125 |A2| 83 |A3| 50 |A1A2| 41 |A1A3| 25 |A2A3| 16 |A1A2A3| 8 154.1.3 容斥原理一般形式n例例4.1.3 确定重集 T3a,4b,5c的10组合的个数。164.1.3 容斥原理一般形式n解一解一 把n个相同球放入标号为a,b,c三个不同盒中,且盒a中最多放3个,盒b中最多放4个,盒c中最多放5个,其不同的方案数计作an,则an(n0,1,2,)的生成函数为174.1.3 容斥原理一般形式 F(x)(x0x1x2x3)
5、(x0x1x2x3 x4 )(x0x1x2x3x4x5 )184.1.3 容斥原理一般形式 故 6194.1.3 容斥原理一般形式n解二解二 令E表示a,b,c的所有10组合的集合,则|E| 66 令 xxE且x中不少于4个a xxE且x中不少于5个b xxE且x中不少于6个c 问题即求 a,b,c的4组合204.1.3 容斥原理一般形式n例4.1.4 把n个不同球放入k个不同盒中,要求每个盒子非空,求其不同的方案数 。214.1.3 容斥原理一般形式n解一解一 (n0,1,2,)的生成函数为224.1.3 容斥原理一般形式n解二解二 把n个不同球放入k个不同盒中,每个盒子的容量不限,其不同方
6、案的集合记作E,则|E| 。令n xxE且盒i为空 (i1,2,k) n问题即求234.1.3 容斥原理一般形式n (t1,2,k) 把n个不同球放入kt个不同盒中,且盒的容 量不限的方案集。n于是244.1.3 容斥原理一般形式n例4.1.5 有n个人,每人先把自己的帽子都放入一个暗室,然后每人再从中任取一顶,求没人能取到自己帽子的概率。254.1.3 容斥原理一般形式n解解 令这n个人各自任取一顶帽子的不同方案的集合为E,则|E|n!。令 xxE且人i取到自己的帽子 (i1,2,n) 没人取到自己帽子的方案数264.1.3 容斥原理一般形式n (t1,2,k) n人各任取一帽子且人1,人2
7、,人t均取到自 己的帽子。n于是 (nt)! (t1,2,n)274.1.3 容斥原理一般形式n故 284.1.3 容斥原理一般形式n所求概率 P 又因 所以 故所求概率为P 0.3679294.1.3 容斥原理一般形式n例4.1.6 求不超过120的素数的个数。304.1.3 容斥原理一般形式n解解 因112121,故不超过120的合数必然是2,3,5,7的倍数,而且不超过120的合数的因子不可能超过11。n设 E1,2,3,120,令n xxE,且x是数i的倍数(i2,3,5,7)314.1.3 容斥原理一般形式n而|A2| 60 |A3| 40 |A5| 24 |A7| 41 |A2A3
8、| 20 |A2A5| 16 |A2A7| 8 |A3A5| 25 324.1.3 容斥原理一般形式n而|A3A7| 5 |A3A2| 3 |A2A3A5|4 |A2A3A7|2 |A2A5A7|1 |A3A5A7|1 |A2A3A5A7|0 334.1.3 容斥原理一般形式n于是 120(60402417)(201288 53)(4211)27 但这27个数未包含2,3,5,7,却包含1,故所 求素数个数为274130344.1.4 Jordan公式公式n设有限集Enp1,p2,pn E中元素的性质集合 nAix|xE且x具有性质pinNk(k0,1,2,n) E中恰好具有k种性质的元素个数
9、 354.1.4 Jordan公式公式n如何求Nk?n比如 N1 ?364.1.4 Jordan公式公式n令 q0 |E| q1 q2 q3 qn 374.1.4 Jordan公式公式n定理4.1.4(Jordan公式公式)nNk 384.1.4 Jordan公式公式n例4.1.7 将原始自然排列1,2,3,n重新作各种排列,求恰有m个元素排在其原来自身位置的排列数。394.1.4 Jordan公式公式n解 记1,2,3,n的所有全排列的集合为E。 Aix|xE且x使数i排在第i位(i1,2,n) 于是 (nt)! (t1,2,n)404.1.4 Jordan公式公式nNm 414.1.4 Jordan公式公式n另解另解 将原始自然排列1,2,3,n重新作各种排列,且恰有m个元素排在其原来自身位置。 一步一步 从n个元素中任取m个元素排在其原来 自身位置 二步二步 其余nm个元素进行错排 Dn-m Nm Dn-mn特别, N0Dn42