清華離散數(shù)學(xué)(第2版)：.ppt

《清華離散數(shù)學(xué)(第2版)：.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《清華離散數(shù)學(xué)(第2版)：.ppt（25頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1,第9章容斥原理,,2,第9章容斥原理,9.1容斥原理9.2對(duì)稱(chēng)篩公式及其應(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相對(duì)于S的補(bǔ)集，i=1,2,…,m.則S中不具有性質(zhì)P1,P2,…,Pm的元素?cái)?shù)為,5,,證明,,證明方法：數(shù)學(xué)歸納法、組合分析證組合分析.若x不具有任何性質(zhì)，則對(duì)等式右邊貢獻(xiàn)為：1?0+0?0+…+(?1)m?0=1若x具有n條性質(zhì)，1?n?m,則對(duì)等式右邊的貢獻(xiàn)為：,6,推論,推論S中至少具有其中一條性質(zhì)的元素?cái)?shù)為,,,證,7,應(yīng)用——計(jì)數(shù)多重集的r-組合數(shù),例1求多重集B={3?a,4?b,5?c}的10-組合數(shù)解：令S={x|x是a,b,c任意重復(fù)的10-組合}A1={x|x?S，x中至少含4個(gè)a}={x|x是a,b,c的任意6-組合}A2={x|x?S，x中至少含5個(gè)b}={x|x是a,b,c的任意5-組合}A3={x|x?S，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求不超過(guò)120的素?cái)?shù)個(gè)數(shù)解：112=121，不超過(guò)120的合數(shù)的素因子可能是2,3,5,7，S={x|x?Z,1?x?120},|S|=120被2,3,5,7整除的集合分別為A1,A2,A3,A4：|A1|=60，|A2|=40，|A3|=24，|A4|=17|A1?A2|=20,|A1?A3|=12,|A1?A4|=8,|A2?A3|=8,|A2?A4|=5,|A3?A4|=3|A1?A2?A3|=4,|A1?A2?A4|=2,|A1?A3?A4|=1,|A2?A3?A4|=1，|A1?A2?A3?A4|=0,N=27+3.,10,應(yīng)用——?dú)W拉函數(shù)的值,,,例3計(jì)算歐拉函數(shù)的值?(n).歐拉函數(shù)：小于n且與n互素的自然數(shù)的個(gè)數(shù)解n的素因子分解式:Ai={x|0?x?n?1，且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對(duì)稱(chēng)篩公式及其應(yīng)用對(duì)稱(chēng)篩公式錯(cuò)位排列計(jì)數(shù)9.2.2棋盤(pán)多項(xiàng)式與有限制條件的排列布棋方案與有限制條件排列的對(duì)應(yīng)棋盤(pán)多項(xiàng)式及其性質(zhì)布棋方案數(shù)的計(jì)數(shù),9.2對(duì)稱(chēng)篩公式及其應(yīng)用,13,對(duì)稱(chēng)篩公式,,令,|S|=N,對(duì)稱(chēng)篩公式:(容斥原理的特殊情況)使用條件：不同性質(zhì)對(duì)計(jì)數(shù)的影響對(duì)稱(chēng).各性質(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í)例,,例18個(gè)字母A,B,C,D,E,F,G,H的全排列中，使得4個(gè)字母不在原來(lái)位置的排列數(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ù)分類(lèi)計(jì)數(shù).將n!個(gè)排列按照出現(xiàn)錯(cuò)位的個(gè)數(shù)分類(lèi)計(jì)數(shù)歸納證明將Dn的值代入取極限,17,排列與布棋方案,一個(gè)棋盤(pán)由大小相同的正方形方格構(gòu)成，一個(gè)方格中允許放入一個(gè)棋子.在向棋盤(pán)布棋時(shí)，要求任何兩個(gè)棋子既不能布在棋盤(pán)的同一行，也不能布在同一列上.,排列i1i2…in表示:第一行的棋子放在第i1列第二行的棋子放在第i2列…第n行的棋子放在第in列,步棋方案,排列：251364,?,18,排列與n個(gè)棋子在n?n棋盤(pán)的布棋方案一一對(duì)應(yīng)位置有限制的排列與有禁區(qū)的步棋方案一一對(duì)應(yīng),布棋方案與棋盤(pán)多項(xiàng)式,rk(C)表示k個(gè)棋子在棋盤(pán)C上的布棋方案數(shù)，則稱(chēng),為棋盤(pán)多項(xiàng)式,位置受限的排列：251364一般表示：i1i2…i6ij?j,j=1,2,…,6,?,?,19,棋盤(pán)多項(xiàng)式的性質(zhì),,Ci：去掉某個(gè)給定方格所在的行和列之后剩余棋盤(pán)Cl：去掉某個(gè)給定方格之后剩余棋盤(pán)C1和C2表示兩個(gè)分離的棋盤(pán)則不難證明：,20,簡(jiǎn)單棋盤(pán)多項(xiàng)式的結(jié)果,21,有禁區(qū)的排列,,限制某些數(shù)字不能出現(xiàn)在某些位置的排列，對(duì)應(yīng)于有禁區(qū)的放棋方案.有下述計(jì)數(shù)定理.定理9.2C是n?n的具有給定禁區(qū)的棋盤(pán)，禁區(qū)對(duì)應(yīng)于{1,2,…,n}的元素在排列中不允許出現(xiàn)的位置，則這種有禁區(qū)的排列數(shù)為中ri是i個(gè)棋子布置到禁區(qū)的方案數(shù)使用條件：棋盤(pán)為n?n,小禁區(qū),22,定理證明,證不考慮禁區(qū)限制，不帶編號(hào)棋子的布棋方案數(shù):n!，考慮棋子編號(hào)，布棋方案數(shù):n!n!Pj:第j個(gè)棋子落入禁區(qū)的性質(zhì)，j=1,2,…,n給定的1個(gè)棋子落入禁區(qū)的方案數(shù):N1=r1(n?1)!(n?1)!給定的2個(gè)棋子落入禁區(qū)的方案數(shù):N2=2!r2(n?2)!(n?2)!…給定的k個(gè)棋子落入禁區(qū)的方案數(shù):Nk=k!rk(n?k)!(n?k)!…n個(gè)棋子落入禁區(qū)的方案數(shù)：Nn=n!rn0!0!,23,定理證明（續(xù)）,,帶編號(hào)的棋子不落入禁區(qū)的方案數(shù):N0不帶編號(hào)的棋子不落入禁區(qū)的方案數(shù):N兩者關(guān)系：N0=Nn!,24,應(yīng)用實(shí)例——工作分配,N=4!?6?3!+10?2–4=24–36+20–4=4,解：禁區(qū)的棋盤(pán)多項(xiàng)式為,根據(jù)定理9.2得,例2G,L,W,Y4位工作人員，A,B,C,D為4項(xiàng)工作.每個(gè)人不能從事的工作如圖中棋盤(pán)的禁區(qū)所示.問(wèn)有多少種分配方案？,25,應(yīng)用實(shí)例——錯(cuò)排問(wèn)題,,例3錯(cuò)位排列的禁區(qū)是主對(duì)角線上的所有方格關(guān)于禁區(qū)的棋盤(pán)多項(xiàng)式如下：,