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

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

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