《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
