離散數(shù)學(xué)--9.1-2容斥原理.ppt

1,第9章 容斥原理,2,第9章 容斥原理,9.1 容斥原理 9.2 對稱篩公式及其應(yīng)用,3,9.1 容斥原理,9.1.1 容斥原理的基本形式 容斥原理 容斥原理的推論 9.1.2 容斥原理的應(yīng)用 計(jì)數(shù)多重集的r-組合數(shù) 計(jì)數(shù)限制條件的元素?cái)?shù) 計(jì)算歐拉函數(shù)的值 證明組合恒等式,4,容斥原理的基本形式,定理9.1 設(shè)S為有窮集，P1,P2, , Pm是m種性質(zhì)，Ai是S中具有性質(zhì)Pi 的元素構(gòu)成的子集， 是Ai 相對于S 的補(bǔ)集， i=1, 2, , m. 則 S 中不具有性質(zhì)P1, P2, , Pm的元 素?cái)?shù)為,5,證明,證明方法：數(shù)學(xué)歸納法、組合分析 證 組合分析. 若 x 不具有任何性質(zhì)，則對等式右邊貢獻(xiàn)為： 1 0 + 0 0 + +(1)m0 = 1 若 x 具有n 條性質(zhì)，1nm, 則對等式右邊的貢獻(xiàn)為：,6,推論,推論 S 中至少具有其中一條性質(zhì)的元素?cái)?shù)為,證,7,應(yīng)用計(jì)數(shù)多重集的r-組合數(shù),例1 求多重集 B = 3a, 4b, 5c 的 10-組合數(shù) 解：令 S = x | x 是 a, b, c 任意重復(fù)的10-組合 A1 = x | xS，x 中至少含4個(gè) a = x | x 是 a, b, c 的任意 6-組合 A2 = x | xS，x 中至少含 5 個(gè) b = x | x 是 a, b, c 的任意 5- 組合 A3 = x | xS，x 中至少含 6 個(gè)c = x | x 是 a, b, c 的任意 4-組合,8,計(jì)數(shù)多重集的r-組合數(shù)（續(xù)）,注意：性質(zhì)的設(shè)定與要求條件相反 性質(zhì)彼此獨(dú)立，不同性質(zhì)的元素計(jì)數(shù)互不影響,9,應(yīng)用計(jì)數(shù)限制條件的元素?cái)?shù),例2 求不超過120 的素?cái)?shù)個(gè)數(shù) 解：112 = 121，不超過120的合數(shù)的素因子可能是2,3,5,7， S = x | xZ, 1x120 , |S| = 120 被2, 3, 5, 7 整除的集合分別為 A1, A2, A3, A4： |A1| = 60，|A2| = 40，|A3| = 24，|A4| = 17 |A1A2|= 20, |A1A3|=12, |A1A4|=8, |A2A3|=8, |A2A4|=5, |A3A4|=3 |A1A2A3|=4, |A1A2A4|=2, |A1A3A4|=1, |A2A3A4|=1，|A1A2A3A4|=0,N=27+3.,10,應(yīng)用歐拉函數(shù)的值,例3 計(jì)算歐拉函數(shù)的值(n). 歐拉函數(shù) ：小于 n 且與 n 互素的自然數(shù)的個(gè)數(shù) 解 n 的素因子分解式: Ai = x | 0xn1，且 pi 整除 x ，,11,應(yīng)用證明交錯(cuò)和的恒等式,證：S=1,2,n, A=1,2,m，計(jì)數(shù)S 中包含A的r-子集. Pj: 在S 的 r-子集中不包含 j, j =1, 2, , m,例4 證明,12,9.2.1 對稱篩公式及其應(yīng)用 對稱篩公式 錯(cuò)位排列計(jì)數(shù) 9.2.2 棋盤多項(xiàng)式與有限制條件的排列 布棋方案與有限制條件排列的對應(yīng) 棋盤多項(xiàng)式及其性質(zhì) 布棋方案數(shù)的計(jì)數(shù),9.2 對稱篩公式及其應(yīng)用,13,對稱篩公式,令, |S|=N, 對稱篩公式: (容斥原理的特殊情況) 使用條件： 不同性質(zhì)對計(jì)數(shù)的影響對稱. 各性質(zhì)計(jì)數(shù)是獨(dú)立的.,14,應(yīng)用錯(cuò)位排列計(jì)數(shù),錯(cuò)位排列數(shù)記作 Dn , 設(shè) S 為 1, 2, , n 的排列的集合， Pi 是其中 i 在第 i 位的性質(zhì)，i=1, 2, , n.,15,錯(cuò)位排列實(shí)例,例1 8個(gè)字母 A, B, C, D, E, F, G, H 的全排列中，使得4個(gè) 字母不在原來位置的排列數(shù).,解：4個(gè)字母的錯(cuò)排數(shù)為,16,錯(cuò)位排列的性質(zhì),3. Dn為偶數(shù)當(dāng)且僅當(dāng)n為奇數(shù).,4. 當(dāng) n 充分大時(shí)，Dn/n! 趨向于1/e.,證明思路： 使用組合分析，按照第 1 位是什么數(shù)分類計(jì)數(shù). 將 n! 個(gè)排列按照出現(xiàn)錯(cuò)位的個(gè)數(shù)分類計(jì)數(shù) 歸納證明 將 Dn 的值代入取極限,17,排列與布棋方案,一個(gè)棋盤由大小相同的正方形方格構(gòu) 成，一個(gè)方格中允許放入一個(gè)棋子. 在向棋盤布棋時(shí)，要求任何兩個(gè)棋子 既不能布在棋盤的同一行，也不能布 在同一列上.,排列 i1 i2 in 表示: 第一行的棋子放在第 i1 列 第二行的棋子放在第 i2 列 第 n 行的棋子放在第 in 列,步棋方案,排列： 2 5 1 3 6 4,18,排列與 n 個(gè)棋子在 nn 棋盤的布棋方案一一對應(yīng) 位置有限制的排列與有禁區(qū)的步棋方案一一對應(yīng),布棋方案與棋盤多項(xiàng)式,rk(C) 表示 k 個(gè)棋子在棋盤 C上的布棋方案數(shù)，則稱,為棋盤多項(xiàng)式,位置受限的排列： 2 5 1 3 6 4 一般表示： i1 i2 i6 ij j, j = 1, 2, , 6,19,棋盤多項(xiàng)式的性質(zhì),Ci ：去掉某個(gè)給定方格所在的行和列之后剩余棋盤 Cl ：去掉某個(gè)給定方格之后剩余棋盤 C1 和 C2 表示兩個(gè)分離的棋盤 則不難證明：,20,簡單棋盤多項(xiàng)式的結(jié)果,21,有禁區(qū)的排列,限制某些數(shù)字不能出現(xiàn)在某些位置的排列，對應(yīng)于有禁 區(qū)的放棋方案.有下述計(jì)數(shù)定理. 定理9.2 C 是 nn 的具有給定禁區(qū)的棋盤，禁區(qū)對應(yīng)于 1,2, , n的元素在排列中不允許出現(xiàn)的位置，則這種有 禁區(qū)的排列數(shù)為 中ri 是 i 個(gè)棋子布置到禁區(qū)的方案數(shù) 使用條件： 棋盤為 nn, 小禁區(qū),22,定理證明,證 不考慮禁區(qū)限制，不帶編號棋子的布棋方案數(shù): n!， 考慮棋子編號，布棋方案數(shù): n! n! Pj: 第 j 個(gè)棋子落入禁區(qū)的性質(zhì) ，j =1, 2, , n 給定的1個(gè)棋子落入禁區(qū)的方案數(shù): N1=r1(n1)!(n1)! 給定的2個(gè)棋子落入禁區(qū)的方案數(shù): N2=2! r2 (n2)!(n2)! 給定的k個(gè)棋子落入禁區(qū)的方案數(shù): Nk=k! rk (nk)! (nk)! n個(gè)棋子落入禁區(qū)的方案數(shù)： Nn=n! rn 0! 0!,23,定理證明（續(xù)）,帶編號的棋子不落入禁區(qū)的方案數(shù): N0 不帶編號的棋子不落入禁區(qū)的方案數(shù): N 兩者關(guān)系：N0=N n!,24,應(yīng)用實(shí)例工作分配,N = 4! 63! + 10 2 4 = 24 36 + 20 4 = 4,解：禁區(qū)的棋盤多項(xiàng)式為,根