清华离散数学(第2版)：9.1-2.ppt

《清华离散数学(第2版)：9.1-2.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、第9章容斥原理1第9章容斥原理9.1容斥原理9.2对称筛公式及其应用29.1容斥原理9.1.1容斥原理的基本形式容斥原理容斥原理的推论9.1.2容斥原理的应用计数多重集的r-组合数计数限制条件的元素数计算欧拉函数的值证明组合恒等式3容斥原理的基本形式定理9.1设S为有穷集，P1,P2,…,Pm是m种性质，Ai是S中具有性质Pi的元素构成的子集，是Ai相对于S的补集，i=1,2,…,m.则S中不具有性质P1,P2,…,Pm的元素数为4证明证明方法：数学归纳法、组合分析证组合分析.若x不具有任何性质，则对

2、等式右边贡献为：10+00+…+(1)m0=1若x具有n条性质，1nm,则对等式右边的贡献为：5推论推论S中至少具有其中一条性质的元素数为证6应用——计数多重集的r-组合数例1求多重集B={3a,4b,5c}的10-组合数解：令S={x

3、x是a,b,c任意重复的10-组合}A1={x

4、xS，x中至少含4个a}={x

5、x是a,b,c的任意6-组合}A2={x

6、xS，x中至少含5个b}={x

7、x是a,b,c的任意5-组合}A3={x

8、xS，x中至少含6个c}={x

9、x是a,b,c的

10、任意4-组合}7计数多重集的r-组合数（续）注意：性质的设定与要求条件相反性质彼此独立，不同性质的元素计数互不影响8应用——计数限制条件的元素数例2求不超过120的素数个数解：112=121，不超过120的合数的素因子可能是2,3,5,7，S={x

11、xZ,1x120},

12、S

13、=120被2,3,5,7整除的集合分别为A1,A2,A3,A4：

14、A1

15、=60，

16、A2

17、=40，

18、A3

19、=24，

20、A4

21、=17

22、A1A2

23、=20,

24、A1A3

25、=12,

26、A1A4

27、=8,

28、A2A3

29、=8,

30、A2A4

31、

32、=5,

33、A3A4

34、=3

35、A1A2A3

36、=4,

37、A1A2A4

38、=2,

39、A1A3A4

40、=1,

41、A2A3A4

42、=1，

43、A1A2A3A4

44、=0N=27+3.9应用——欧拉函数的值例3计算欧拉函数的值(n).欧拉函数：小于n且与n互素的自然数的个数解n的素因子分解式:Ai={x

45、0xn1，且pi整除x}，10应用——证明交错和的恒等式证：S={1,2,…,n},A={1,2,…,m}，计数S中包含A的r-子集.Pj:在S的r-子集中不包含j,j=1,2,…,m例4证明119.2

46、.1对称筛公式及其应用对称筛公式错位排列计数9.2.2棋盘多项式与有限制条件的排列布棋方案与有限制条件排列的对应棋盘多项式及其性质布棋方案数的计数9.2对称筛公式及其应用12对称筛公式令,

47、S

48、=N,对称筛公式:(容斥原理的特殊情况)使用条件：不同性质对计数的影响对称.各性质计数是独立的.13应用——错位排列计数错位排列数记作Dn,设S为{1,2,…,n}的排列的集合，Pi是其中i在第i位的性质，i=1,2,…,n.14错位排列实例例18个字母A,B,C,D,E,F,G,H的全排列中，使得4个字母不在

49、原来位置的排列数.解：4个字母的错排数为15错位排列的性质3.Dn为偶数当且仅当n为奇数.4.当n充分大时，Dn/n!趋向于1/e.证明思路：使用组合分析，按照第1位是什么数分类计数.将n!个排列按照出现错位的个数分类计数归纳证明将Dn的值代入取极限16排列与布棋方案一个棋盘由大小相同的正方形方格构成，一个方格中允许放入一个棋子.在向棋盘布棋时，要求任何两个棋子既不能布在棋盘的同一行，也不能布在同一列上.排列i1i2…in表示:第一行的棋子放在第i1列第二行的棋子放在第i2列…第n行的棋子放在第in列

50、步棋方案排列：251364⇕17排列与n个棋子在nn棋盘的布棋方案一一对应位置有限制的排列与有禁区的步棋方案一一对应布棋方案与棋盘多项式rk(C)表示k个棋子在棋盘C上的布棋方案数，则称为棋盘多项式位置受限的排列：251364一般表示：i1i2…i6ijj,j=1,2,…,6⇕⇔18棋盘多项式的性质Ci：去掉某个给定方格所在的行和列之后剩余棋盘Cl：去掉某个给定方格之后剩余棋盘C1和C2表示两个分离的棋盘则不难证明：19简单棋盘多项式的结果20有禁区的排列限制某些数字不能出现在某些位置的排列，对应

51、于有禁区的放棋方案.有下述计数定理.定理9.2C是nn的具有给定禁区的棋盘，禁区对应于{1,2,…,n}的元素在排列中不允许出现的位置，则这种有禁区的排列数为中ri是i个棋子布置到禁区的方案数使用条件：棋盘为nn,小禁区21定理证明证不考虑禁区限制，不带编号棋子的布棋方案数:n!，考虑棋子编号，布棋方案数:n!n!Pj:第j个棋子落入禁区的性质，j=1,2,…,n给定的1个棋子落入禁区的方案数:N1=r1(n1)!(n1)!给定的2个棋子落入禁区