第三章容斥原理與鴿巢

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

2、3=133§3.1容斥原理引論若A和B是集合U的子集，補集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è)x Î A U B ,則 x Ï A U B相當于 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即定理對n+1也是正確的。6§3.2容斥原理最簡單的計數(shù)問題是求有限集合A和B的并的元素數(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容斥原理進一步可推出：=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容斥原理例 一個學(xué)校只有三門課程：數(shù)學(xué)、物理、化學(xué)。已知修這三門課的學(xué)生分別有170、130、120人；同時修數(shù)學(xué)、物理兩門課的學(xué)生45人；同時修數(shù)學(xué)、化學(xué)的20人；同時修物理化學(xué)的22人。同時修三門的3人。問這學(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時k=2時k=3時C(2,k) = 1 21 2k=1時k=2時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)中每個子集再加上元素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對n用歸納法。n=2時，等式成立。 假設(shè)對n - 1，等式成立。對于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的元素個數(shù)，即不屬于A的元素個數(shù)等于集合的全體減去屬于A的元素的個數(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|計算不在 A1 也不在 A2中的元素個數(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計算不滿足任意屬性的元素.å+L+(-A Ç A ÇÇ Am1)L12mX不滿足任何屬性11-0-0+(-1)

15、m0 = 1X只滿足1個屬性01-1-0 +(-1)m0 = 0X只滿足n個屬性, 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兩邊相等，同樣計算不滿足任何屬性的元素個數(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六個字母的全排列中不例1出現(xiàn)ace和df圖象的排列數(shù)。解：6個字母全排列： |S| = 6!設(shè)A為ace作為一個元素出現(xiàn)的排列集: |A|=4!，B為 df作為一個元素出現(xiàn)的排列集: |B|=5!，AB為同時出現(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ù)的個數(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ù)的個數(shù)為=A +-A U BBA I B=21§3.3 舉例 例3 求由a,b,c,d四個字母的n位符號串中，a,b,c都 至少出現(xiàn)一次的符號串數(shù)目。 解：令A(yù)、B、C分別為n位符號串中不出現(xiàn)a，b，c符號的集 合。由于n位符號

20、串中每一位都可取a，b，c，d四種符號中的一出現(xiàn)a的n位符號串的個數(shù)應(yīng)是3n個，即：個，故不= 3n= 1BCAA I B I C= 2nA I BA I CC I Ba，b，c至少出現(xiàn)一次的n位符號串集合即為= 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。求不超過120的素數(shù)個數(shù)。 因112=121，故不超過120的合數(shù)必然是2、3、5、7的 倍數(shù)，而且不超過120的合數(shù)的因子不可能都超過11。設(shè)Ai為不超過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注意：因為27個數(shù)中排除+I A5A3 I A7A5 I A7了2，3，5，7四個素數(shù)，-A2I A3I A5A2 I A3 I A7又包含了1這個非素數(shù)。故

24、所求的不超過120的素數(shù)個+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個英文字母作不重復(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個布爾變量確定的布爾函數(shù)的個數(shù)。260 00 11 01 1f(x1,x2)f(x1,x2,xn)中n個f100000布爾變量的不同的f20001x1 Ù x 2f30010x1 Ù x 2狀態(tài)數(shù)為2n 每個狀態(tài)有0，1兩f40011x1f50100x1 Ù x 2種取值，f60101x2f70110x1 Ù x 2 故f(x1,x2,xn)的布n爾函數(shù)個數(shù)為 22f80111(x1Ú2)f91000x1 &#

27、218; x 2f101001x1 Ù x 2f111010(x1Ú2)f121011x 2f131100x1 Ú x 2f141101x1f151110x1 Ú x 2f1611111n22f(x1,x2,xn)的布爾函數(shù)個數(shù)為 例6。求完全由n個布爾變量確定的布爾函數(shù)的個數(shù)。n )中xi不出現(xiàn)的布爾函數(shù)類為：Ai ， i = 1, 2,., n.解：設(shè) f (n-1C (n,1) 22n-2C (n,2) 22有1個變量不出現(xiàn)的布爾函數(shù)個數(shù)為有2個變量不出現(xiàn)的布爾函數(shù)個數(shù)為n-kC (n, k ) 22有k個變量不出現(xiàn)的布爾函數(shù)個數(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時，得2= 22- C (2,1)22 + C (2, 2)2A I A1227 = 16 - 8 + 2 = 10§3.3 舉例例6。求完全由n個布爾變量確定的布爾函數(shù)的個數(shù)。280 00 11 01 1f(x1,x2)f(x1,x2,xn)中n個f100000布爾變量的不同的f20001x1 Ù x 2f30010x1 Ù x 2狀態(tài)數(shù)為2n 每個狀態(tài)有0，1兩f

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

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

31、的個數(shù)。 ap a2 . pakn = pn分解為不同素數(shù)的乘積解：若112k| A |= n , i =1,2.k設(shè)1到n的n個數(shù)中為p 倍數(shù)的集合為Aiiipi對于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ù)的個數(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無公因子的數(shù)有16個：7，11，13，17，19，23，29，31，37，41，43，47，49，53，59，此外還有一個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ù)目。解：對于x1+x2+xn=r的非負整數(shù)解的個數(shù)為C(n+r-1,r)沒有約束情況下的不定方程x1+x2+x3=15的非負整數(shù)解的個數(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的非負整數(shù)解個數(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ù)解個數(shù)相等?x1+x2+x3=150x1,x2,x3 10顯然不成立,所以原解法不具有通用性 應(yīng)加上約束條件11+2+2=15x1=11x2=2x3=2找不到對應(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解個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: 錯排問題: n個元素依次給以標號1，2，n。n個元素的全排列中，求每個元素都不在原來位置上的排列數(shù)。設(shè)Ai為數(shù)i在第i位上的全體排列，i=1，2，n。因數(shù)字i不能動，因而有：|Ai|=(n-1)!|AiAj |=(n-2)!每個元素都不在原來位置的排列數(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個字母A,B,C,D,E,F,G,H的全排列中,求使A,C,E,G四個字母不在原來上的錯排數(shù)目。解：8個字母的全排列中，令A(yù)A,AC,AE,AG分別表A,C,E,G在原來位置上的排列，則錯排數(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個字母A,B,C,D,E,F,G,H的全排列中只 有4個不在原來位置的排列數(shù)。解：8個字母中只有4個不在原來位置上，其余4個字母保持不動，相當于4個

39、元素的錯排，其數(shù)目為4!(1 - 1 +111 )-+1!2!3!4!= 24(1 -1 + 1 - 1 +1) = 92624 故8個字母的全排列中有4個不在原來位置上的排列數(shù) 39應(yīng)為：C(8,4)·9=630§3.4棋盤多項式和有限制排列1.有限制排列4個x ，3個y，2個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；全排列的個數(shù)為： 所以： |A1A2A3|=1260(60+105+280)+(12+20+30)6=87140§3.4棋盤多項式和有限制排列 棋盤多項式 n個不同元素的一個全排列可看做n個相同的棋子在n×n的棋盤上的一個布局。布局滿足同一行（列）中有且僅有一個棋子non-attacking rooks12345xP1的布局對應(yīng) xP2于排列41352。xP3xP4xP541§3.4棋盤多項式和有限制排列可以把棋盤的形狀推廣到任意

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

42、，則 r1(C)nr1(C)r0(Ci) + r1(Ce)，r1(Ce)n1 r0(Ci)1故規(guī)定 r0(C)1是合理的44§3.4棋盤多項式和有限制排列該性質(zhì)擴展到棋盤多項式，從而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棋盤多項式和有限制排列 例如：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棋盤多項式和有限制排列性質(zhì)2:如果C由相互分離的C1，C2組成，即C1的任一格子所在的行和列中都沒有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棋盤多項式和有限制排列 利用（）和（），可以把一個比較復(fù) 雜的棋盤逐步分解成相對比較簡單的棋盤，從而得到其棋盤多項式。例R () = xR()+R()*= x(