容斥原理組合數(shù)學(xué)

容斥原理組合數(shù)學(xué)[解]2得倍數(shù)就是:2,4,6,8,10,12,14,16,18,20。共10個(gè);3.1容斥原理例1,求[1,20]中2或3得倍數(shù)得數(shù)得個(gè)數(shù)、否！因?yàn)?,12,18在兩類中重復(fù)計(jì)數(shù),應(yīng)減去。3得倍數(shù)就是:3,6,9,12,15,18。共6個(gè);答案就是10+6=16個(gè)嗎？故答案就是:16-3=13

容斥原理研究有限集合得交或并得計(jì)數(shù)。則有3.1容斥原理(b)[DeMorgan定理]論域U,A得補(bǔ)集(a)(1)3.1容斥原理證:(a)得證明相當(dāng)于和同時(shí)成立，亦即若則反之，若故(2)由(1)與(2)得(b)得證明與(a)類似,從略、3.1容斥原理DeMogan定理得推廣:證明:只證(a)、n=2時(shí),定理已證。設(shè)定理對(duì)n就是正確得,即假定:3.1容斥原理設(shè)正確即定理對(duì)n+1也就是正確得。3.1容斥原理

最簡單得計(jì)數(shù)問題就是求有限集合A與B得并得元素?cái)?shù)目。顯然有即具有性質(zhì)A或B得元素得個(gè)數(shù)等于具有性質(zhì)A得元素個(gè)數(shù)與具有性質(zhì)B得元素個(gè)數(shù)減去同時(shí)具有性質(zhì)A與B得元素個(gè)數(shù)。(1)定理13.1容斥原理UBA3.1容斥原理3.1容斥原理證若A∩B=φ,則

|A∪B|=|A|+|B|,否則同理|B|＝|B∩A|+|B∩A|(2)|A|＝|A∩(B∪B)|

＝|(A∩B)∪(A∩B)|

＝|A∩B|+|A∩B|(1)3.1容斥原理|A∪B|－|A|－|B|＝|A∩B|+|A∩B|+|B∩A|

－(|A∩B|+|A∩B|)

－(|B∩A|+|B∩A|)＝－|A∩B|(3)－(1)－(2)得∴|A∪B|＝|A|+|B|－|A∩B|大家有疑問的，可以詢問和交流可以互相討論下，但要小聲點(diǎn)3.1容斥原理證明定理23.1容斥原理3.1容斥原理ABC例2,一個(gè)學(xué)校只有三門課程:數(shù)學(xué)、物理、化學(xué)。已知修這三門課得學(xué)生分別有170、130、120人;同時(shí)修數(shù)學(xué)、物理兩門課得學(xué)生45人;同時(shí)修數(shù)學(xué)、化學(xué)得20人;同時(shí)修物理化學(xué)得22人。同時(shí)修三門得3人。問這學(xué)校共有多少學(xué)生？3.1容斥原理解:令M為修數(shù)學(xué)得學(xué)生集合;

P

為修物理得學(xué)生集合;

C為修化學(xué)得學(xué)生集合;則即學(xué)校學(xué)生數(shù)為336人。3.1容斥原理同理可推出:利用數(shù)學(xué)歸納法可得一般得定理:3、1容斥原理3、1容斥原理證對(duì)n用歸納法。n=2時(shí),等式成立。

假設(shè)對(duì)n-1,等式成立。對(duì)于n有定理3設(shè)

(n,k)就是［1,n］得所有k-子集得集合,則3、1容斥原理3.1容斥原理(4)定理3’設(shè)是有限集合，則此定理也可表示為:其中N就是集合U得元素個(gè)數(shù)、即不屬于A得元素個(gè)數(shù)等于集合得全體減去屬于A得元素得個(gè)數(shù)、一般有:3.1容斥原理(5)容斥原理指得就就是(4)與(5)式。解:設(shè)A為ace作為一個(gè)元素出現(xiàn)得排列集,B為df作為一個(gè)元素出現(xiàn)得排列集,A

B為同時(shí)出現(xiàn)ace、df得排列數(shù)。3.1容斥原理例3求a,b,c,d,e,f六個(gè)字母得全排列中不允許出現(xiàn)ace與df圖象得排列數(shù)。根據(jù)容斥原理,不出現(xiàn)ace與df得排列數(shù)為:=6!-(5!+4!)+3!=582例4求從1到500得整數(shù)中能被3或5除盡得數(shù)得個(gè)數(shù)、3.1容斥原理解:令A(yù)為從1到500得整數(shù)中被3除盡得數(shù)得集合,B為被5除盡得數(shù)得集合被3或5除盡得數(shù)得個(gè)數(shù)為解:令A(yù)、B、C分別為n位符號(hào)串中不出現(xiàn)a,b,c符號(hào)得集合。由于n位符號(hào)串中每一位都可取a,b,c,d四種符號(hào)中得一個(gè),故不允許出現(xiàn)a得n位符號(hào)串得個(gè)數(shù)應(yīng)就是3^n即有3.1容斥原理例5求由a,b,c,d四個(gè)字母構(gòu)成得位符號(hào)串中,a,b,

c,d至少出現(xiàn)一次得符號(hào)串?dāng)?shù)目。a,b,c至少出現(xiàn)一次得n位符號(hào)串集合即為3.1容斥原理例6,求不超過120得素?cái)?shù)個(gè)數(shù)。

因11×11=121,故不超過120得合數(shù)必然就是2、3、5、7得倍數(shù),而且不超過120得合數(shù)得因子不可能都超過11。設(shè)

Ai為不超過120得數(shù)i得倍數(shù)集,i=2,3,5,7。3.1容斥原理3.1容斥原理3.1容斥原理3、1容斥原理3.1容斥原理

注意:27并非就就是不超過120得素?cái)?shù)個(gè)數(shù),因?yàn)檫@里排除了2,3,5,7著四個(gè)數(shù),又包含了1這個(gè)非素?cái)?shù)。2,3,5,7本身就是素?cái)?shù)、故所求得不超過120得素?cái)?shù)個(gè)數(shù)為:27+4-1=30

例7,用26個(gè)英文字母作不允許重復(fù)得全排列,要求排除dog,god,gum,depth,thing字樣得出現(xiàn),求滿足這些條件得排列數(shù)。3.1容斥原理解:所有排列中,令出現(xiàn)dog字樣得排列,相當(dāng)于把dog作為一個(gè)單元參加排列,故類似有:由于god,dog不可能在一個(gè)排列中同時(shí)出,故:類似:3.1容斥原理

由于gum,dog可以在dogum字樣中同時(shí)出現(xiàn)，故有：

類似有g(shù)od和depth可以在godepth字樣中同時(shí)出現(xiàn)，故

god和thing可以在thingod字樣中同時(shí)出現(xiàn)，從而

3.1容斥原理3.1容斥原理

由于god、depth、thing不可以同時(shí)出現(xiàn),

故有:其余多于3個(gè)集合得交集都為空集。3.1容斥原理

故滿足要求得排列數(shù)為:

例8，求完全由n個(gè)布爾變量確定的布爾函數(shù)的個(gè)數(shù)。

由于n個(gè)布爾變量x1,x2,…xn

的不同的真值表數(shù)目與位2進(jìn)制數(shù)數(shù)目相同，故為個(gè)。根據(jù)容斥原理，滿足條件的函數(shù)數(shù)目為：3.1容斥原理解:設(shè)f(x1,x2,…xn)中xi不出現(xiàn)得布爾函數(shù)類為3.1容斥原理3.1容斥原理這10個(gè)布爾函數(shù)為：x1∧x2，x1∧x2，x1∧x2，x1∧x2，x1∨x2，x1∨x2，x1∨x2，x1∨x2，(x1∨x2)∧(x1∨x2)，(x1∨x2)∧(x1∨x2)

例9。歐拉函數(shù)

(n)就是小于n且與n互素得數(shù)得個(gè)數(shù)。

設(shè)1到n得n個(gè)數(shù)中為pi倍數(shù)得集合為則有3.1容斥原理解:若n分解為素?cái)?shù)得乘積3.1容斥原理3.1容斥原理即比60小且與60無公因子得數(shù)有16個(gè):7,11,13,17。19。23,29,31,37,41,43,47,49,53,59,此外尚有一個(gè)1。3.1容斥原理1,再解錯(cuò)排問題

n個(gè)元素依次給以標(biāo)號(hào)1,2,…,n。n個(gè)元素得全排列中,求每個(gè)元素都不在自己原來位置上得排列數(shù)。設(shè)Ai

為數(shù)i在第i位上得全體排列,i=1,2,…,n。因數(shù)字i不能動(dòng),因而有:3.2容斥原理—應(yīng)用同理每個(gè)元素都不在原來位置得排列數(shù)為3、2容斥原理—應(yīng)用

例1。數(shù)1,2,…,9得全排列中,求偶數(shù)在原來位置上,其余都不在原來位置得錯(cuò)排數(shù)目。3、2容斥原理—應(yīng)用解:實(shí)際上就是1,3,5,7,9五個(gè)數(shù)得錯(cuò)排問題,總數(shù)為:例2,在8個(gè)字母A,B,C,D,E,F,G,H得全排列中,求使A,C,E,G四個(gè)字母不在原來上得錯(cuò)排數(shù)目。解:8個(gè)字母得全排列中,令

A1

A2

A3

A4分別表A,C,E,G在原來位置上得排列,則錯(cuò)排數(shù)為:3.2容斥原理—應(yīng)用例3。求8個(gè)字母A,B,C,D,E,F,G,H得全排列中只有4個(gè)不在原來位置得排列數(shù)。解:8個(gè)字母中只有4個(gè)不在原來位置上,其余4個(gè)字母保持不動(dòng),相當(dāng)于4個(gè)元素得錯(cuò)排,其數(shù)目為:3.2容斥原理—應(yīng)用故8個(gè)字母得全排列中有4個(gè)不在原來位置上得排列數(shù)應(yīng)為:C(8,4)·9=6302、有限制排列3、2、容斥原理—應(yīng)用解設(shè)出現(xiàn)xxxx得排列得集合記為A1,則設(shè)出現(xiàn)yyy得排列得集合記為A2,則4!2!7!=105；|A2|=6!1!·3!·2!=60;|A1|=例4

4個(gè)x,3個(gè)y,2個(gè)z得全排列中,求不出現(xiàn)xxxx,yyy,zz圖象得排列。3.2.容斥原理—應(yīng)用設(shè)出現(xiàn)zz得排列得集合記為A3,4!·3!8!|A3|=

=280；4!2!|A1∩A2|==125!3!|A1∩A3|==20；6!4!|A2∩A3|==309!2!·3!·4!全排列的個(gè)數(shù)為：

=1260；|A1∩A2∩A3|=3!=6所以|A1∩A2∩A3|=1260－(60+105+280)+(12+20+30)－6=8713.2.容斥原理—應(yīng)用3、棋子多項(xiàng)式

n個(gè)不同元素得一個(gè)全排列可瞧做n個(gè)相同得棋子在n×n得棋盤上得一個(gè)布局。布局滿足同一行(列)中有且僅有一個(gè)棋子xxxxx

如圖所示得布局對(duì)應(yīng)于排列41352。3.2.容斥原理—應(yīng)用

可以把棋盤得形狀推廣到任意形狀:

布子規(guī)定稱為無對(duì)攻規(guī)則,棋子相當(dāng)于象棋中得車。

令r

k(C)表示k個(gè)棋子布到棋盤C上得方案數(shù)。如:3.2.容斥原理—應(yīng)用r1()=1，r1()=2，r1()=2，r2()=0，r2()=1。為了形象化起見,()中得圖象便就是棋盤得形狀。3.2.容斥原理—應(yīng)用定義1設(shè)C為一棋盤，稱R(C)=∑rk(C)xk為C的棋盤多項(xiàng)式。k=0∞規(guī)定r0(C)=1,包括C=Ф時(shí)。設(shè)Ci就是棋盤C得某一指定格子所在得行與列都去掉后所得得棋盤;Ce就是僅去掉該格子后得棋盤。在上面定義下,顯然有rk(C)=rk－1(Ci)＋rk(Ce),3.2.容斥原理—應(yīng)用即對(duì)任一指定得格子,要么布子,所得得方案數(shù)為

rk－1(Ci);要么不布子,方案數(shù)為

rk(Ce)。

設(shè)C有n個(gè)格子,則

r1(C)＝n、r1(C)＝r0(Ci)+r1(Ce),∵r1(Ce)＝n－1∴r0(Ci)＝1、故規(guī)定

r0(C)＝1就是合理得、3.2.容斥原理—應(yīng)用

從而

R(C)=∑rk(C)xk

＝１＋∑[rk－1(Ci)+

rk(Ce)]xk=x∑rk(Ci)xk+∑rk(Ce)xk

＝xR(Ci)+R(C

e)(3)∞k=0∞k=1∞k=0∞k=03.2.容斥原理—應(yīng)用例如:R()=1+x；R()=xR()+R()=x+(1+x)=1+2x；R()=xR()+R()=x(1+x)+1+x=1+2x+x23.2.容斥原理—應(yīng)用

如果C由相互分離得C1,C2組成,即C1得任一格子所在得行與列中都沒有C2得格子。則有:

R(C)=∑(∑ri(C1)rk-i(C2))xk

=(∑ri(C1)xi)(∑rj(C2)xj)j=0nnkni=0i=0k=0∴R(C)=R(C1)R(C2)(4)i=0krk(C)=∑ri(C1)rk－i(C2)故3.2.容斥原理—應(yīng)用利用(３)與(４),可以把一個(gè)比較復(fù)雜得棋盤逐步分解成相對(duì)比較簡單得棋盤,從而得到其棋盤多項(xiàng)式。例

R()=xR()+R()=x(1+x)2+(1+2x)2=1+5x+6x2+x3*R()=xR()+R()=1+6x+10x2+4