第三章容斥原理與鴿巢

1、第三章 容斥原理與鴿巢原理馬昱春myc1第三章 容斥原理與鴿巢原理InclusionandExclusionPrinciple計(jì)數(shù)時(shí)重疊部分不能被重復(fù)計(jì)算容斥的計(jì)數(shù)思想是: 先不考慮重疊的情況，把包含于某內(nèi)容中的所有對(duì)象的數(shù)目先計(jì)算出來(lái)； 然后再把計(jì)數(shù)時(shí)重復(fù)計(jì)算的數(shù)目排斥出去； 使得計(jì)算的結(jié)果既無(wú)遺漏又無(wú)重復(fù)。2 容斥原理ABAB§3.1容斥原理引論1，20中2或3的倍數(shù)的個(gè)數(shù)例解 2的倍數(shù)是： 2，4，6，8，10，12，14，16，18，20。10個(gè)3的倍數(shù)是：3，6，9，12，15，18。6個(gè)不是10+6=16 個(gè)，因?yàn)?，12，18但 在兩類中重復(fù)計(jì)數(shù)，應(yīng)減去。 故是：16-

2、3=133§3.1容斥原理引論若A和B是集合U的子集，補(bǔ)集complementA = x | x ÎU 且x Ï A德摩根De Morgan定理(a)A U B = A I B(b)A I B = A U BUAB4(a)A U B =A I B證：(a)的證明。x Ï B同時(shí)設(shè)x Î A U B ,則 x Ï A U B相當(dāng)于 x Ï A和成立，亦即xÎ AU B Þ xÎ AI B(1)反之，若 x Î A I B, 即x Î A和x Î B故 x Ï

3、 A, x Ï B即x Ï A U B x Î A I B Þ x Î A U B(2)由（1）和（2）得 x Î A I B Û x Î A U B(b)的證明和(a)類似，從略.5§3.1容斥原理引論DeMogan定理的推廣：設(shè)A1,A2, . An是U的子集,(a)A1 U A2 U . U An = A1 I A2 I . I An則證:采用數(shù)學(xué)歸納法A1 U A2 U . U An= A1 I A2 I. I An正確則= ( A1 U. U An ) U An+1A1 U A2 U. U An

4、U An+1= ( A1 U A2 U. U AnI An+1= A1 I A2 I. I AnI An+1即定理對(duì)n+1也是正確的。6§3.2容斥原理最簡(jiǎn)單的計(jì)數(shù)問(wèn)題是求有限集合A和B的并的元素?cái)?shù)目。證若AB=，則 | AB |= |A| + |B| A | A ( BB) | (AB)(AB)| AB | + | AB |( 1 )同理| B | | BA | + | BA | AB |(A( BB)(B(AA)|( 2 )|(AB)(AB)(BA)(BA)| AB| + |AB | + | BA|( 3 )(3)-(2)-(1) 得到| AB | A | B | AB| + |

5、AB | + | BA| ( | AB | + | AB | )( | BA | + | BA | )7| AB | A | + | B | AB | | AB |A U B=A+B-A I B(1)§3.2容斥原理定理：(2)-+B I CA I B I C-A I C8A U B U C=A+B+C-A I B§3.2容斥原理證明：=A U B U C( A U B) U C=+ C- ( A U B) I CA U B( A U B) I C = ( A I C) U (B I C)根據(jù)=A + C-A U B U CBA I B- ( A I C) U (B I C

6、) = A + B + C - A I B - A I C - B I C9+A I B I C§3.2容斥原理進(jìn)一步可推出：=A +B + C+ D -A U B U C U DA I B- A I C - B I C-A I D +A I B I C+A I B I D + B I C I D -A I B I C I D10§3.2容斥原理例 一個(gè)學(xué)校只有三門(mén)課程：數(shù)學(xué)、物理、化學(xué)。已知修這三門(mén)課的學(xué)生分別有170、130、120人；同時(shí)修數(shù)學(xué)、物理兩門(mén)課的學(xué)生45人；同時(shí)修數(shù)學(xué)、化學(xué)的20人；同時(shí)修物理化學(xué)的22人。同時(shí)修三門(mén)的3人。問(wèn)這學(xué)校共有多少學(xué)生？令：M為修

7、數(shù)學(xué)的學(xué)生集合；P 為修物理的學(xué)生集合；C 為修化學(xué)的學(xué)生集合；= 170,= 130, C= 120, M I P= 45PM= 20, P I C= 22, M I P I C= 3M I CM- 20 - 22 + 311即學(xué)校學(xué)生數(shù)為336人。= 336-M I C-P I C+M I P I CM U P U C=M+P+C-M I PC(3,k) = 1 2 31 21 32 31 2 3k=1時(shí)k=2時(shí)k=3時(shí)C(2,k) = 1 21 2k=1時(shí)k=2時(shí)C(3,2) = 1 32 31 2定理設(shè)C(n,k)是1,n的所有k-子集的集合, 則nnååIA |i

8、ii =1k =1I ÎC ( n ,k )iÎ I證: 分析C(n,k)，可根據(jù)包含不包含n劃分成兩部分包含n的可看做C(n-1,k-1)中每個(gè)子集再加上元素n；不包含n的由C(n-1,k)組成；å IååA |=IIA |+I|A|A |k2iiniIÎC(n,k) iÎIIÎC(n-1,k-1) iÎIIÎC(n-1,k) iÎI對(duì)n用歸納法。n=2時(shí)，等式成立。 假設(shè)對(duì)n - 1，等式成立。對(duì)于n有12nnåk = 1å=( - 1) k -1U| IAA|

9、iii = 1I Î C ( n , k )iÎ In-1n-1n-1n-1n-1n=+ | A | -=+ | A | -UUUUUUUAAAAA I AnA(A I An )iininiini證i=1i=1i=1i=1i=1i=1n-1n-1n-1åiåånåå I i=| A | +(-|A |+| A | -(-k1I ik11)1)|(A IA )|ni=1k=2IÎC(n-1,k) iÎIk=1IÎC(n-1,k)iÎIn-1n-1n-1nååå

10、;|A |+ | A | +å(-1)k-1åk -n-=| A | +(-1II+ (-1I1)|( AI A ) |1)|A |iininii=1k =2IÎC ( n-1,k ) iÎIk =2IÎC ( n-1,k -1) iÎIi=1i =1k =2IÎC ( n,k ) iÎIi =1n= å(-1)k-1k =1å | I Ai |IÎC ( n,k )iÎI13nn-1= å| A | +å(-1)k-1iå | I Ai |n+

11、 (-1)n-1 | I A |i由于å |IAi |=å |IAi IAn |+å |IAi |IÎC(n,k) iÎIIÎC(n-1,k-1) iÎIIÎC(n-1,k) iÎIn-1n-1= å(-1)k-1k=1å |IAi |IÎC(n-1,k) iÎI+| A | -å(-1)k-1nk=1å |I(Ai IAn |IÎC(n-1,k) iÎI§3.2容斥原理k - 1此定理也可表示為：A1 U A2U

12、. U Annni =1i =1j >in+ååå- .I AjI AkAii=1 j>i k>j(4)+(-1)n-1A I AI . I A12n14= åAi- ååAiI AjnnU A ii = 1= å ( - 1)k = 1å| I A i|I Î C ( n , k )iÎ I§3.2容斥原理= N -A ,又A其中N是集合U的元素個(gè)數(shù)，即不屬于A的元素個(gè)數(shù)等于集合的全體減去屬于A的元素的個(gè)數(shù)。一般有：= N -A1 I A2 I . I AnA1 U

13、 A2U . U An-1 U Annn= N - å+ ååAiAiI Aji=1i=1j >in(5)-ååå Ai+ .I AjI Aki=1 j>i k>j+ (-1)nA I A I . I A1512nInclusion-Exclusion Principle| A1 I A2 |=| S | - | A1 | - | A2| + | A1 I A2|計(jì)算不在 A1 也不在 A2中的元素個(gè)數(shù)若x 不屬于A1 或A211-0-0+0 = 1若x 屬于A1 但不屬于A201-1-0+0 = 0若x 屬于A2

14、但不屬于A101-0-1+0 = 0若x 屬于A2 且屬于A101-1-1+1 = 0 兩邊相等16(x+y)m =C(m,0)xm+ C(m,1)xm-1y+C(m,m)ym If x=1, y=-10 = C(m,0)- C(m,1) +(-1)mC(m,m)= S -å Ai+å Ai Ç Aj-å Ai Ç Aj Ç AkA1 Ç A2 ÇLÇ Am計(jì)算不滿足任意屬性的元素.å+L+(-A Ç A ÇÇ Am1)L12mX不滿足任何屬性11-0-0+(-1)

15、m0 = 1X只滿足1個(gè)屬性01-1-0 +(-1)m0 = 0X只滿足n個(gè)屬性, n£mC(n,0)-C(n,1)+C(n,2)+(-1)mC(n,m)0= C(n,0)-C(n,1)+C(n,2)+(-1)n) +0 +0=0兩邊相等，同樣計(jì)算不滿足任何屬性的元素個(gè)數(shù)17§3.2容斥原理容斥原理指的就是（4）和（5）式。nn= å Ai- åå AiA1 U A2 U . U AnI Aji=1i=1j >in+ååå Ai- .I Aj I Aki=1 j>i k>j(4)+(-1)n-1A

16、 I AI. I A12n= N -A1 I A2 I. I AnA1 U A2U . U An-1 U Annnn= N - å Ai+ åå Ai-ååå Ai+ .I AjI Aj I Aki=1+ (-1)ni=1j >ii=1 j>i k>j(5)A I A I. I A12n18§3.2容斥原理Inclusionexclusion principle This concept is attributed to Abraham deMoivre (1718) it first appears in

17、 a paper of Daniel da Silva (1854) later in a paper by J. J. Sylvester (1883)"One of the most useful principles of enumeration in discrete probability andcombinatorial theory is the celebrated principle of inclusionexclusion. When skillfully applied, this principle has yielded the solution to m

18、any a combinatorial problem."§3.3 舉例求a,b,c,d,e,f六個(gè)字母的全排列中不例1出現(xiàn)ace和df圖象的排列數(shù)。解：6個(gè)字母全排列： |S| = 6!設(shè)A為ace作為一個(gè)元素出現(xiàn)的排列集: |A|=4!，B為 df作為一個(gè)元素出現(xiàn)的排列集: |B|=5!，AB為同時(shí)出現(xiàn)ace、df的排列數(shù): |AB |=3!。| AIB|=| AUB|=S-| A|-| B|+| AIB|= 6!-4!-5!+3!= 58220§3.3 舉例求從1到500的整數(shù)中能被3或5除盡的數(shù)的個(gè)數(shù)。例2解： 令A(yù)為從1到500的整數(shù)中被3除盡的數(shù)的集合

19、，B為被5除盡的數(shù)的集合= ê 500 ú = 166, B= ê 500 ú = 100;Aêëúûêëúû35= ê 500 ú = 33A I Bêë 15úû被3或5除盡的數(shù)的個(gè)數(shù)為=A +-A U BBA I B=21§3.3 舉例 例3 求由a,b,c,d四個(gè)字母的n位符號(hào)串中，a,b,c都 至少出現(xiàn)一次的符號(hào)串?dāng)?shù)目。 解：令A(yù)、B、C分別為n位符號(hào)串中不出現(xiàn)a，b，c符號(hào)的集 合。由于n位符號(hào)

20、串中每一位都可取a，b，c，d四種符號(hào)中的一出現(xiàn)a的n位符號(hào)串的個(gè)數(shù)應(yīng)是3n個(gè)，即：個(gè)，故不= 3n= 1BCAA I B I C= 2nA I BA I CC I Ba，b，c至少出現(xiàn)一次的n位符號(hào)串集合即為= 4n - ( A+C ) + ( A I BA I B I CB+C I B ) -A I CA I B I C= 4n- 3 · 3n + 3 · 2n -122§3.3 舉例 例4。求不超過(guò)120的素?cái)?shù)個(gè)數(shù)。 因112=121，故不超過(guò)120的合數(shù)必然是2、3、5、7的 倍數(shù)，而且不超過(guò)120的合數(shù)的因子不可能都超過(guò)11。設(shè)Ai為不超過(guò)120的數(shù) i

21、的倍數(shù)集， i=2，3，5，7。= ê120 ú = 60，A= ê120 ú = 40，Aêëúûêëúû2323ê120 úê120 ú= êëúû = 24，A7= êëúû = 17,A557120ê120ê=ú = 20，A=ú = 12,AI AI A2325ë 2 ´ 3 û

22、ë 10û= ê120 ú = 8，A I A= ê120 ú = 8，AI Aêë 14ûúëê 15ûú273523= ê120 ú = 5，A= ê120 ú = 3，AAI AIêëúûêëúû37572135= ê120ú =AAI A4，Iêë 2 ´ 3´ 5 &#

23、250;û235= ê120ú =AAI A2，Iêë 2 ´ 3 ´ 7 úû237= ê120ú = 1，AAI AIêë 2 ´ 5 ´ 7 ûú257= 120 -+-A2 I A3I A5 I A7A2A3A2A5-+A7A3A2 I A3A2 I A5I A7注意：因?yàn)?7個(gè)數(shù)中排除+I A5A3 I A7A5 I A7了2，3，5，7四個(gè)素?cái)?shù)，-A2I A3I A5A2 I A3 I A7又包含了1這個(gè)非素?cái)?shù)。故

24、所求的不超過(guò)120的素?cái)?shù)個(gè)+AI AI A I A2357數(shù)為：= 120 - (60 + 40 + 24 +17) + (20 +12 + 8+ 8 + 5 + 3) - (4 + 2 +1+1)27+4-1=3024= 27.-A2 I A5 I A7-A3 I A5 I A7§3.3 舉例例5。用26個(gè)英文字母作不重復(fù)的全排列，要求排除dog，god，gum，depth，thing字樣的出現(xiàn)，求滿足這些條件的排列數(shù)。解：令A(yù)1為出現(xiàn)dog，| A1 |=24！ 令A(yù)2為出現(xiàn)god，| A2 |=24！令A(yù)3為出現(xiàn)gum，| A3 |=24！令A(yù)4為出現(xiàn)depth，| A4 |=

25、22！ 令A(yù)5為出現(xiàn)thing，| A5 |=22！| A1A2| = 0,A1A3, dogum:| A1A3| = 22!,A2A4, godepth:| A2A4| = 20!, A2A5, thingod:| A2A5| = 20!,A3A4, gum*depth或者gum*depth :| A3A4| = 20！ A3A5, thingum: | A3A5| = 20！A4A5, depthing:| A4A5| = 19!,A1A3 A4,dogumdepth0;A2A4 A5, godepthing0; A3A4 A5, depthingum | A3A4 A5 | = 17！2

26、5所求的排列數(shù)為 26!-(3*24!+2*22!)+(22!+4*20!+19!)-(17!)§3.3 舉例例6。求完全由n個(gè)布爾變量確定的布爾函數(shù)的個(gè)數(shù)。260 00 11 01 1f(x1,x2)f(x1,x2,xn)中n個(gè)f100000布爾變量的不同的f20001x1 Ù x 2f30010x1 Ù x 2狀態(tài)數(shù)為2n 每個(gè)狀態(tài)有0，1兩f40011x1f50100x1 Ù x 2種取值，f60101x2f70110x1 Ù x 2 故f(x1,x2,xn)的布n爾函數(shù)個(gè)數(shù)為 22f80111(x1Ú2)f91000x1 &#

27、218; x 2f101001x1 Ù x 2f111010(x1Ú2)f121011x 2f131100x1 Ú x 2f141101x1f151110x1 Ú x 2f1611111n22f(x1,x2,xn)的布爾函數(shù)個(gè)數(shù)為 例6。求完全由n個(gè)布爾變量確定的布爾函數(shù)的個(gè)數(shù)。n )中xi不出現(xiàn)的布爾函數(shù)類為：Ai ， i = 1, 2,., n.解：設(shè) f (n-1C (n,1) 22n-2C (n,2) 22有1個(gè)變量不出現(xiàn)的布爾函數(shù)個(gè)數(shù)為有2個(gè)變量不出現(xiàn)的布爾函數(shù)個(gè)數(shù)為n-kC (n, k ) 22有k個(gè)變量不出現(xiàn)的布爾函數(shù)個(gè)數(shù)為根據(jù)容斥原理，滿

28、足條件的函數(shù)數(shù)目為：n-1n= 22- C(n,1)22A I AI . I A12nn-2n-k+ C(n, 2)22- . + (-1)k C(n, k )22+ . + (-1)n)2n = 2時(shí)，得2= 22- C (2,1)22 + C (2, 2)2A I A1227 = 16 - 8 + 2 = 10§3.3 舉例例6。求完全由n個(gè)布爾變量確定的布爾函數(shù)的個(gè)數(shù)。280 00 11 01 1f(x1,x2)f(x1,x2,xn)中n個(gè)f100000布爾變量的不同的f20001x1 Ù x 2f30010x1 Ù x 2狀態(tài)數(shù)為2n 每個(gè)狀態(tài)有0，1兩f

29、40011x1f50100x1 Ù x 2種取值，f60101x2f70110x1 Ù x 2 故f(x1,x2,xn)的布n爾函數(shù)個(gè)數(shù)為 22f80111(x1Ú2)f91000x1 Ú x 2f101001x1 Ù x 2f111010(x1Ú2)f121011x 2f131100x1 Ú x 2f141101x1f151110x1 Ú x 2f1611111在計(jì)算機(jī)領(lǐng)域中廣泛使用的RSA公鑰算法也正是以歐拉函數(shù)為基礎(chǔ)的。例7。歐拉函數(shù)F(n)是求小于n且與n互素的數(shù)的個(gè)數(shù)。 分析的化身歐拉進(jìn)行計(jì)算看起來(lái)毫不費(fèi)

30、勁兒，就像人進(jìn)行呼吸，像鷹在風(fēng)中盤(pán)旋一樣。 他是歷史上最多產(chǎn)的數(shù)學(xué)家。 彼得堡學(xué)院為了整理他的著作整整花了47年。 歐拉確實(shí)常常在兩次叫他吃晚飯的一篇數(shù)學(xué)左右的時(shí)間里趕出 人生波折：失明，火災(zāi) 科學(xué)環(huán)境：普魯士腓特烈大帝和葉卡捷琳娜女皇慷慨地給了數(shù)學(xué)以無(wú)法報(bào)償?shù)馁Y助。1783年9月18日，他77歲的時(shí)候，歐拉寫(xiě)出了他對(duì)星軌道的計(jì)算。他在喝著茶跟孩子玩的時(shí)候，中風(fēng)發(fā)作。手中煙斗掉了， 只說(shuō)出一句話"我要死了","歐拉便停止了生命和計(jì)算。"29F(8)=48 = 23，小于8且與8互素有§3.3 舉例 例7。歐拉函數(shù)F(n)是求小于n且與n互素的數(shù)

31、的個(gè)數(shù)。 ap a2 . pakn = pn分解為不同素?cái)?shù)的乘積解：若112k| A |= n , i =1,2.k設(shè)1到n的n個(gè)數(shù)中為p 倍數(shù)的集合為Aiiipi對(duì)于pipj, AiAj既是pi的倍數(shù)也是pj的倍數(shù)。n| A IA |=,i, j =1,2.,k,i ¹ jijp pijy(n)=I . I Aknnnn= n - (+ . +) + (pknnn+ . +) - × ×× ±p p××× ppp p31n12k111= n(1 -)(1 -) ××× (1 -)p1

32、p2pk30111y(n)=n(1 -)(1 -) ××× (1 -)p1p2pk 例7續(xù)。歐拉函數(shù)F(n)是求小于n且與n互素 的數(shù)的個(gè)數(shù)。F(8)=8(1-1/2) = 48 = 23，小于8且與8互素有1 3 5 7例如n = 60 = 22 ´ 3´ 5，則y (60) = 60(1 - 1 )(1 - 1)(1 - 1 ) = 16235即比60小且與60無(wú)公因子的數(shù)有16個(gè)：7，11，13，17，19，23，29，31，37，41，43，47，49，53，59，此外還有一個(gè)1。31例 求不定方程x1+x2+x3=15,求整數(shù)解的數(shù)目

33、。其中附加約束為0x1 5, 0x2 6； 0x3 7,例 求不定方程x1+x2+x3=15,附加約束為0x1 5, 0x2 6； 0x3 7,求整數(shù)解的數(shù)目。解：對(duì)于x1+x2+xn=r的非負(fù)整數(shù)解的個(gè)數(shù)為C(n+r-1,r)沒(méi)有約束情況下的不定方程x1+x2+x3=15的非負(fù)整數(shù)解的個(gè)數(shù)為C(15+3-1,15)= C(17,2)設(shè)A1為x16的解， y1+6+x2+x3=15|A1|= C(9+3-1,9)= C(11,2)設(shè)A2為x27的解， x1+y2+7+x3=15|A2|= C(8+3-1,8)= C(10,2)設(shè)A3為x38的解，x1+x2+ y3+8=15|A3|= C(7+

34、3-1,7)= C(9,2)A1A2:y1+6+y2+7+x3=15 |A1A2|= C(2+3-1,2)= C(4,2)A1A3:y1+6+x2+y3+8=15 |A1A3|= C(1+3-1,1)= C(3,1)A2A3:x1+y2+7+y3+8=15 |A2A3|= 1A1A2 A3 : y1+6+y2+7+y3+8=15; |A1A2 A3 |= 0 |A1A2 A3|=C(17,2) C(11,2)-C(10,2)-C(9,2)33+C(4,2)+C(3,1)+1=10§3.7 容斥原理應(yīng)用舉例例 求不定方程x1+x2+x3=15,附加約束為0x15, 0x26； 0x37

35、,求整數(shù)解的數(shù)目。解2: x1=5-x1, x2=6-x2, x3=7-x3x1+ x2 + x3 =5-x1+6-x2+7-x3=18-(x1+x2+x3) = 3,x1+ x2 + x3 =3C(3+3-1,3) = 10x1, x2, x30的非負(fù)整數(shù)解個(gè)數(shù)。：例3-18，pp13834討論例:求不定方程x1+x2+x3=15,附加約束為0x1 10,0x2 10； 0x3 10,求整數(shù)解的數(shù)目x1=10-x1, x2=10-x2, x3=10-x3x1+ x2 + x3 =10-x1+10-x2+10-x3=15, x1, x2, x30x1+ x2 + x3 =15x1, x2, x

36、30整數(shù)解個(gè)數(shù)相等?x1+x2+x3=150x1,x2,x3 10顯然不成立,所以原解法不具有通用性 應(yīng)加上約束條件11+2+2=15x1=11x2=2x3=2找不到對(duì)應(yīng)的x1,x2,x3 0 x1, x2, x3 10x1=10-x1, x2=10-x2, x3=10-x335討論x1+x2+x3=S0x1 m1, 0x2 m2； 0x3 m3x1=m1-x1, x2=m2-x2, x3=m3-x3x1+ x2 + x3 =m1+m2+m3-S0 x1 m1, x2 m2, x3 m3解個(gè)36 若m1+m2+m3-S min(m1,m2,m3)則 x1+x2+x3=S0x1 m1, 0x2

37、m2； 0x1 m3 x1+ x2 + x3 =m1+m2+m3-S x1, x2, x30整數(shù)數(shù)相等§3.3 舉例 例8: 錯(cuò)排問(wèn)題: n個(gè)元素依次給以標(biāo)號(hào)1，2，n。n個(gè)元素的全排列中，求每個(gè)元素都不在原來(lái)位置上的排列數(shù)。設(shè)Ai為數(shù)i在第i位上的全體排列，i=1，2，n。因數(shù)字i不能動(dòng)，因而有：|Ai|=(n-1)!|AiAj |=(n-2)!每個(gè)元素都不在原來(lái)位置的排列數(shù)為= n!n -1)!A1 I A2 I . I An+- 2)!- ××× -,)1!111 )= n!(1 -+- ××× ±(n -

38、i)!i!i!1!2!n!37C(n, i)(n - i)!=n!(n - i)!= n! 例9 在8個(gè)字母A,B,C,D,E,F,G,H的全排列中,求使A,C,E,G四個(gè)字母不在原來(lái)上的錯(cuò)排數(shù)目。解：8個(gè)字母的全排列中，令A(yù)A,AC,AE,AG分別表A,C,E,G在原來(lái)位置上的排列，則錯(cuò)排數(shù)為：- C(4, 3)5!+ C(4, 4)4! = 2402438A1 I A2 I A3 I A4= 8!- C(4,1)7!+ C(4, 2)6! 求8個(gè)字母A,B,C,D,E,F,G,H的全排列中只 有4個(gè)不在原來(lái)位置的排列數(shù)。解：8個(gè)字母中只有4個(gè)不在原來(lái)位置上，其余4個(gè)字母保持不動(dòng)，相當(dāng)于4個(gè)

39、元素的錯(cuò)排，其數(shù)目為4!(1 - 1 +111 )-+1!2!3!4!= 24(1 -1 + 1 - 1 +1) = 92624 故8個(gè)字母的全排列中有4個(gè)不在原來(lái)位置上的排列數(shù) 39應(yīng)為：C(8,4)·9=630§3.4棋盤(pán)多項(xiàng)式和有限制排列1.有限制排列4個(gè)x ，3個(gè)y，2個(gè)z的全排列中，求不出現(xiàn)x，yyy，zz圖象的排列。例x的排列的集合記為A1，解設(shè)出現(xiàn)|A1|=6 !=60;3 ! 2 !設(shè)出現(xiàn)yyy的排列的集合記為A2， 7 ! | A2|=105；4 !2 !設(shè)出現(xiàn)zz的排列的集合記為A2， 8 ! | A3|=280；4 !3!4 !5 !|A1A2|=12

40、； |A1A3|=20；2 !3!6 !|A2A3|=30； |A1A2A3|=3!=6；4 !9!/(4!*3!*2!) =1260；全排列的個(gè)數(shù)為： 所以： |A1A2A3|=1260(60+105+280)+(12+20+30)6=87140§3.4棋盤(pán)多項(xiàng)式和有限制排列 棋盤(pán)多項(xiàng)式 n個(gè)不同元素的一個(gè)全排列可看做n個(gè)相同的棋子在n×n的棋盤(pán)上的一個(gè)布局。布局滿足同一行（列）中有且僅有一個(gè)棋子non-attacking rooks12345xP1的布局對(duì)應(yīng) xP2于排列41352。xP3xP4xP541§3.4棋盤(pán)多項(xiàng)式和有限制排列可以把棋盤(pán)的形狀推廣到任意

41、形狀：令r k（C）表示k個(gè)棋子布到棋盤(pán)C上的方案數(shù)。如：)=2， r1(r2()=1。r2()=0，42r1()=1， r1()=2，§3.4定義棋盤(pán)多項(xiàng)式和有限制排列n設(shè)C為一棋盤(pán)，稱R(C)= r (C) xkkk=0為C的棋盤(pán)多項(xiàng)式。規(guī)定 r0(C)=1，包括C=時(shí)。性質(zhì)1:設(shè)Ci是棋盤(pán)C的某一指定格子所在的行與列都去掉后所得的棋盤(pán)；Ce是僅去掉該格子后的棋盤(pán)，則 rk(C)=rk1(Ci)rk(Ce)要么布子，方案數(shù)為 rk-1(Ci)；要么不布子，方案數(shù)為 rk(Ce)。CiCe43對(duì)任一指定的格子，*§3.4棋盤(pán)多項(xiàng)式和有限制排列r0(C)1 ?設(shè)C有n個(gè)格子

42、，則 r1(C)nr1(C)r0(Ci) + r1(Ce)，r1(Ce)n1 r0(Ci)1故規(guī)定 r0(C)1是合理的44§3.4棋盤(pán)多項(xiàng)式和有限制排列該性質(zhì)擴(kuò)展到棋盤(pán)多項(xiàng)式，從而nR(C)= r (C) xkkk=0nrk1(Ci)+ rk(Ce)xkk=1n-1n= x rk(Ci)xk + rk(Ce)xkk=0k=0xR(Ci) + R(C e)(3)45§3.4棋盤(pán)多項(xiàng)式和有限制排列 例如：R()=1+ x；R()= xR()+ R() =x+ (1+ x)=1+2x；R()= x R() + R()= x(1 + x )+1 + x=1+ 2x +x246§3.4棋盤(pán)多項(xiàng)式和有限制排列性質(zhì)2:如果C由相互分離的C1，C2組成，即C1的任一格子所在的行和列中都沒(méi)有C2的格子。則有：krk(C) = ri(C1) rki(C2)i=0nkR(C) = ( ri(C1) rki(C2) ) xk故k=0i=0nn=( ri(C1) xi) ( rj(C2) xj )j=0i=0R(C) = R(C1) R(C2)(4)47§3.4棋盤(pán)多項(xiàng)式和有限制排列 利用（）和（），可以把一個(gè)比較復(fù) 雜的棋盤(pán)逐步分解成相對(duì)比較簡(jiǎn)單的棋盤(pán)，從而得到其棋盤(pán)多項(xiàng)式。例R () = xR()+R()*= x(