排列組合的生成

1、3.計(jì)數(shù) Counting3.1 排列 Permutations（置換）3.1.1 乘積集合Product Sets,卡氏積 Cartesian Product設(shè) A,B 是兩個(gè)集合，元素a A, bB，稱 (a,b)為一個(gè)序?qū)Γ蛐蚺紀(jì)rdered pair。(a,b)=(c,d)當(dāng)且僅當(dāng) a=c b=d定義乘積集合AB =(a,b)| aA,bB 定理 1乘法原理 Multiplication Priciple|A B|=|A| |B|假設(shè)依次實(shí)行 T 1,T 2 兩種任務(wù)，如果做T1 有 n1 種不同的辦法 , 做 T2 有 n2 種不同的辦法 , 則共有 n1n2 種方法完成任務(wù) T1

2、T2。定理 2乘法原理推廣|A 1 A 2A k|=|A1 | |A2|A k|假設(shè)依次實(shí)行任務(wù) T1, T2, ,T k,如果做 T 1 有 n1 種不同的辦法 , 做 T2 有 n2 種不同的辦法 , 做 Tk 有 nk 種不同的辦法 , 則共有 n1 n2 nk 種方法完成任務(wù) T1 T2 Tk。例 1 a) 用 1，2，3， 4， 5 可以組成多少個(gè)不同的三位數(shù)？b)用 0，1，2，3，4， 5 可以組成多少個(gè)不同的三位數(shù)？解 a) 第一位有 5 種取法，第二位，第三位也都有 5 種取法，共組成 53 =125 個(gè)不同的三位數(shù)。b) 第一位有 5 種取法，第二位，第三位有 6 種取法，

3、共組成 5 62 =180 個(gè)不同的三位數(shù)。例 2n 個(gè)元素的集合 A 共有多少個(gè)子集？解由第一章知可以用 n 個(gè) 1 的數(shù)組表示 A,A 的子集可以用長度為n 的 0，1 序列表示。每一位可以取 0 或 1，兩種取法，共有 2 2 2 2=2n 種不同的 01 串，對應(yīng) 2n 個(gè)不同的子集。定理 3.從 n 個(gè)元素的集合 A 中可重復(fù)地取出r 個(gè)元素排成一列，共有 n r 種不同的取法。定理 4.從 n 個(gè)元素的集合 A 中不重復(fù)地取出r 個(gè)元素排成一列，共有 n(n-1)(n-r+1) 種不同的取法。簡稱n 個(gè)元素中取 r 個(gè)元素的排列 Permuations有P rn 種，排列 Pnrn

4、!n r= n(n-1) (n-r+1)=(nr )!=全排列從 n 個(gè)元素的集合A 中不重復(fù)地取出n 個(gè)元素排成一列，共有 n! 種不同的取法。簡稱 n 個(gè)元素的全排列 Permuations 有 Pn 種， Pn =n! 。重集有重復(fù)元素的集合collectiona,a,a,b,c,a,b,b,c,c,c,a,a,a,b,b,c,c,c,c分別記作3a,b,c, a,2b,3c, 3a,2b,4c重集的全排列3a,b,c 的全排列，看成 5 個(gè)元素的全排列共5！個(gè)。其中3 個(gè) a 與不同次序無關(guān)，每個(gè)排列重復(fù)出現(xiàn)3！次。去除重復(fù)共有不同的排列5!3!=20 個(gè)。a,2b,3c 的全排列，看

5、成 6 個(gè)元素的全排列共6！個(gè)。其中 2 個(gè) b 與 3 個(gè) c 不同次序無6!關(guān)，每個(gè)排列重復(fù)出現(xiàn)2！ 3! 次。去除重復(fù)共有不同的排列2!3!=60 個(gè)。9! 3a,2b,4c 的全排列，共有3!2!4! =1260 個(gè)定理 5. n 個(gè)元素的重集 k 1a1,k 2a2 ,klal的不同的全排列共有n!k1! k2!kl ! 個(gè)。例英文單詞 BANANA 中所有字符組成的不同的全排列有多少個(gè)？6!3!2!1! =60 個(gè)3.2 組合 Combinations定理 1. n 個(gè)物體中一次取出r 個(gè)不同元素的組合，共有Cnrn!r !(n r )! 種不同取法。CnrPnrn rn!r !r

6、!r! (n r )! 。例 1.52 張撲克牌中一次取5 張，有多少不同的取法C525 52 5!55251504948=54321=2,598,9603.2.1 無窮重集的組合na 1,a2, ,ankna1,a2, ,anka1a1| a2 a2a2 | a3 | an an an an0010 001100 00k 0 n-11(nk 1)! = Cnnk11 = Cnkk 1(n1)! k!n(n 1)( nk1)n k=k!=k!kCnkn k2. na 1,a2, ,ank 1 =k!例 2一個(gè)電臺有獎(jiǎng)競猜獎(jiǎng)品為十佳 CD 中可重復(fù)地任選三張，問有多少種不同的選法？33 1 =C

7、3=10 3=121110=220C10123!321na 1,a2,ankna 1,a2, ,ank-nCnk (nk n) 1 = Ckk 1n = Ckn 11n knn(n 1)(k 1)k 1 k nk1 n 1(kn)! =(kn)!= (kn)! =(n1)!推論 3. n 個(gè)元素的集合 a1,a2,an 中可重復(fù)地取k 個(gè)元素，每個(gè)元素至少取一個(gè)的組合數(shù)為 Ckn 11例 3. 四種月餅裝盒， 每盒 8 塊，每種月餅至少一塊， 一共可裝多少種不同的月餅盒？解 相當(dāng)于每盒 4 塊月餅，共可裝3765C7= 321 =35 種。3.2.2 有窮重集的組合3.k k1,k2 , ,k

8、n, n k 1a1,k2a2, ,knan k Cnk k 1kk1,k2,kn,例 4. 求重集 3a, 4b, 5c 中取 10 個(gè)元素的組合數(shù)。解法 1.令 A= a, b, c.A的 10組合數(shù)C122= 1211 =66P(a): A 的 10 組合中多于3 個(gè) a :2A的6組合數(shù)C82P(b): A 的 10 組合中多于4 個(gè) b :A的5組合數(shù)C72P(c): A 的 10 組合中多于5 個(gè) c :A的4組合數(shù)C62P(a)P(b): A 的 10 組合中多于 3 個(gè) a ,4 個(gè) b: A 的 1 組合數(shù)C32P(a) P(c): A 的 10 組合中多于3 個(gè) a ,5

9、個(gè) c: A 的 0 組合數(shù)C22P(b) P(c): A 的 10 組合中多于 4 個(gè) b,5 個(gè) c:A 的-1 組合數(shù)0P(a) P(b)P(c): A 的 10 組合中多于3 個(gè) a ,4 個(gè) b, 5 個(gè) c:A 的-5 組合數(shù)066C2 C2 C 2+C2+C2 =6876323a, 4b, 5c1062.3a, 4b, 5c 102C322 1= C42=6.x1+x2+xn=kk 1 a1 ,k2a2, ,knankCnkk 1x12n=k11 2 2n n+x +xka ,k a ,k a k,Ckn115.x12 36+x +xx1+x2+x3=3C2212 3C2x +x

10、 +x =43x1+x2+x3=5C42x1+x2+x3=6C5223223654C 2C3C4C 5= C6=321=206. 2n+12n+1C22n 3 x1+x2<x3,x1+x2+ x3< 2x3,x3>2n12n+1x3 n+1x2 n+1x1 n+1相當(dāng)于三人分 n 個(gè)蘋果：共有 Cn2 2于是 , 任意兩個(gè)之和都不少于第三人的分法有，2n(n 1)C2 n 3 3 Cn22 =2種。3.3 鴿籠原理Pigeonhole PrincipleTheorem 1(The pigeonhole principle)n 個(gè)鴿子放進(jìn) m個(gè)鴿籠里，如果 m<n,則至少

11、有一個(gè)鴿籠放兩個(gè)或兩個(gè)以上鴿子。例 1 信息學(xué)院一二年級學(xué)生中一定有生日相同的學(xué)生。解 信息學(xué)院一二年級共有學(xué)生400 人， 400>366, 所以至少有兩人同一生日。例 2從 1 到 8 中任選 5 個(gè)數(shù)，其中必有相加得9 的兩個(gè)數(shù)。證明 將 1-8 分成四個(gè)不同集合 A =1,8, A=2,7, A3=3,6, A=4,5.121由鴿籠原理，任選 5 個(gè)數(shù)至少有兩個(gè)在一組，相加得9。例 3從 1-20 中任選 11 個(gè)數(shù)一定有一個(gè)是另一個(gè)的倍數(shù)。證明 . 任意一個(gè)數(shù)都可以分解為若干個(gè)2 和一個(gè)奇數(shù)的乘積：n=2k mm是奇數(shù)。klk l，則 n1|n2, 反之 n2|n1.設(shè) n =

12、2 m,n=2 m有相同的奇數(shù)因子，若121-20 中任意一個(gè)數(shù)的奇數(shù)因子都小于20，至多 10 個(gè)。由鴿籠原理，11 個(gè)數(shù)中至少有兩個(gè)有相同的奇數(shù)因子。因此一個(gè)是另一個(gè)的倍數(shù)。例 4 任意 6 個(gè)人中一定有三個(gè)人互相認(rèn)識，或有三個(gè)人互相不認(rèn)識。證明用6 個(gè)點(diǎn) a1,a 2,a 6 表示 6個(gè)人，兩人認(rèn)識用一條紅色邊相連，兩人不認(rèn)識用一條藍(lán)色邊相連。我們證明這個(gè)圖中一定有一個(gè)紅色三角形，或藍(lán)色三角形。從某一點(diǎn) a1 出發(fā)有 5 條邊， 由鴿籠原理一定有一種顏色的三條邊，比如有三條紅色邊, 相連的三個(gè)點(diǎn)為 a2,a 3,a 4。如果 a2,a3,a 4 三點(diǎn)中有紅色邊，則他們與a1 組成一個(gè)紅色

13、三角形。如果 a ,a ,a4三點(diǎn)中沒有紅色邊，則a ,a ,a組成一個(gè)藍(lán)色三角形。23234廣義鴿籠原理 The Extended Pigeonhole Principlen 個(gè)鴿子放進(jìn) m個(gè)鴿籠，則必有一個(gè)鴿籠至少放(n-1)/m+1 個(gè)鴿子。例 5100 個(gè)人中至少有 9 個(gè)人同月出生。解由廣義鴿籠原理(100-1)/12+1=93.4 概率基礎(chǔ)Elements of Probability樣本 Sample一次測試得到的結(jié)果叫樣本。樣本空間 Sample Space一個(gè)測試的所有結(jié)果組成的集合叫樣本空間。例 1 擲兩個(gè)硬幣不同的觀察方法可以得到的樣本空間：看幾個(gè)國徽：A1=0,1,2分

14、別兩個(gè)正反面：A2=HH,HT,TH,TT看兩個(gè)硬幣同正反：A3=M,N樣本空間要先決定，可以無限。本書只考慮有限樣本空間。例 2一個(gè)骰子擲兩次，得到兩個(gè)數(shù)字，樣本空間：A=(n,m)|1n,m 6, |A|=36.例 3.盒子里又四個(gè)一分和五個(gè)一毛硬幣， 依次從盒子里取出三個(gè)硬幣， 得到的樣本空間：A=PPP,PPD,PDP,PDD,DPP,DPD,DDP,DDD |A|=8.事件 Events測試結(jié)果適合某種特定條件的陳述。事件可以用適合條件的樣本集合表示。例 4. (a) 例 2 中兩次和為 8 的事件B=(2,6),(3,5),(4,4),(5,3),(6,2).|B|=5.(b) 例

15、 2 中兩次和至少為 10 的事件C=(4,6),(5,5),(5,6),(6,4),(6,5),(6,6)|C|=6必然事件 certain event：事件的集合=樣本空間不可能事件 impossible event事件的集合=空集事件的運(yùn)算如果 E,F 是事件，則事件 EF發(fā)生事件 EF發(fā)生E F, E F,E 也是事件。事件 E或 F發(fā)生。事件 E和 F都發(fā)生。事件 E 發(fā)生事件 E 不發(fā)生。例 5擲骰子測試，事件E 是讀數(shù)為偶數(shù)E=2,4,6,事件 F 是讀數(shù)為素?cái)?shù)F=2,3,5.E F=2,3,4,5,6讀數(shù)是偶數(shù)或素?cái)?shù)。E F =2讀數(shù)既是偶數(shù)又是素?cái)?shù)。E =1， 3， 5 讀數(shù)

16、不是偶數(shù) .互相排斥或互相獨(dú)立事件事件 E,F 稱為互相排斥或互相獨(dú)立mutually exclusive， or disjoint，如果 E F=, E,F不交 . 即 E,F 不能同時(shí)發(fā)生。事件 E1,E 2 ,E n 稱為互相排斥, 互相獨(dú)立mutually exclusive， or disjoint，如果其中任意兩個(gè)互相排斥或互相獨(dú)立。若Ei 發(fā)生，則其他事件都不會(huì)發(fā)生。事件 E 的概率 p(E), probability of the event E事件的頻率frequency of occurrence of the event EnE總共測試n 次，其中事件E 發(fā)生 nE 次，

17、事件E 發(fā)生的頻率fE =n事件的概率 probability of the event E測試次數(shù)充分大時(shí)，頻率f E 的極限叫 E 的概率 p(E)例 6擲骰子測試，正面向上和反面向上的概率都是1/2概率的性質(zhì)P1: 0p(E)1,對任何 E A.P2: p(A)=1, p()=0 .P3:如果 事件 E1,E 2,E n 互相排斥 , 互相獨(dú)立，則p(E 1 E2 En)= p(E 1 )+p(E 2 )+p(E n).稱 P1,P2,P3 為概率公理。滿足概率公理 P1,P2,P3 的一個(gè)概率叫做概率空間 probability space 。設(shè) A 是一個(gè)概率空間， A= x 1,x

18、 2,x n 每個(gè) xk 叫做基本事件 elementary event 。令 p =p(xk) 叫基本概率 elementarykprobability，由概率公理EP1: 0pk1EP2: p+p +p =112n已知基本概率p1， p2， ， pn，就可以計(jì)算任意事件E 的概率。例 8假設(shè)一個(gè)測試的樣本空間A=1,2,3,4,5,6, 基本概率如下：p1=p2 =p6=1/12, p3=1/3, p 4=1/6, p5=1/4,事件 E=2,4,6,則 p(E)=1/12+1/6+1/12=1/3.等概率事件假設(shè)基本概率都相等，則p1=p2=pn=1/n.p(xi1,xi2,xi3)=3

19、/n.E=xi1,xi2,xik| E |P(E)= | A |例 9從 52 張撲克牌中隨機(jī)選取4 張牌，選到 4 張 k 的概率是多少？解 這是等概率事件， 從 52 張撲克牌中選取 4 張牌的取法共有 C524 種，取得 4 張 king 的概率 p(E)=1/ C524 .例 10從裝有六個(gè)紅球和四個(gè)綠球的盒子里隨機(jī)選取四個(gè)球，選到兩個(gè)紅球兩個(gè)綠球的概率是多少？解 一盒 10 個(gè)球，選 4 個(gè)共有 C104種，6 個(gè)紅球中選出 2 個(gè)，共有 C 62種， 4 個(gè)綠球中兩個(gè)共有C42種，由乘法原理10 個(gè)球中選出兩紅兩綠共有C62 C42 種。C62C42156C4P(E)=210 =0

20、.428571.10例 11一個(gè)正六面體骰子擲三次，事件 E 為三個(gè)數(shù)字相同或一個(gè)都不是 4。求 p(E).解. 這也是等概率事件。一個(gè)骰子擲一次，可得6 個(gè)數(shù)，擲三次可得63 個(gè)可能的結(jié)果。E= FGF: 三次讀數(shù)相同。G: 沒有 4。|F|=6,|G|=125, |FG|=5,|E|=|F|+|G|-|F G|=126p(E)=126/216=7/12.例 12從裝有六個(gè)紅球和四個(gè)綠球的盒子里隨機(jī)選取四個(gè)球。(a) 事件 E是紅球不多于2 個(gè)，求 p(E).(b) 事件 F 是紅球不多于 3 個(gè)，求 p(F).解（ a）令 E= E0 E1 E2E0 表示不取紅球|E 0|=1E1 表示取

21、一個(gè)紅球|E 1|=24E2 表示取二個(gè)紅球|E 2|=90E0, E1，E2 互相獨(dú)立。|E|=|E 0 E1 E2|=|E 0|+|E 1|+|E 2|=115p(E)=115/210=23/42(b) F = E 4 ,|E 4|=15,p( F )=p(E)=15/210=1/14p(F)=1-p(F )=1-1/14=13/14.概率常用于計(jì)算機(jī)算法平均時(shí)間復(fù)雜性的估計(jì)。例 13從長度為 10 的數(shù)組中查找一個(gè)關(guān)鍵詞所需的平均計(jì)算步驟為等概率事件（ 1+2+3+ +10） /10=5.53.5 遞推關(guān)系Recurrence Relations例 1Fibonacci Sequence

22、 菲波納奇數(shù)列(a) an=an-1+1, a1=4等差數(shù)列 .(b) fn=fn-1+f n-2,f1=f2=1.遞推關(guān)系必須有 (a)初始條件 initial condition, 要有 (b)遞推條件 recurrence condition。令 A=0,1, 以 cn 表示 A* 中長度為 n，不含連續(xù)兩個(gè) 0 的串的個(gè)數(shù)，給出 cn 的遞推關(guān)系：c1=2：0， 1c2=3：01， 10， 11c3=5：010， 011， 101， 110， 111cn0*, 1* 兩種，不能 00，只有 01#和 1* 兩種#是長 n-2 串， * 是長 n-1 串遞推公式cn=cn-1+cn-2初

23、始條件c1=2，c2=3。cn=fn+2回溯法從遞推關(guān)系 recurrence relaion 求顯示公式 explicitformula例 4(1) an=an-1+3, a1=2an=an-1+3 =an-2+2 3 an=an-3+3 3=a1+(n-1)3=2+3(n-1)(2) bn=2bn-1+1,b1=72bn+1=2bn-1+2=2(bn-1+1)=2 (bn-2+1)bn=2n+2-1k 階線性齊次遞推關(guān)系an= r 1an-1 + r 2an-2+ r kan-k特征方程characteristic equationxn= r 1 xn-1 + r 2xn-2+ r kxn

24、-k定理 1.(1) 如果遞歸關(guān)系的an = r 1 an-1 + r 2 an-2 特征方程 x2= r 1x + r 2 有兩個(gè)不同的根x1, x 2，則數(shù)列的顯式通項(xiàng)公式是 :an=c1x1n+c2x2n其中常數(shù)c1,c2 由初始條件確定。(2) 如果特征方程x2 = r 1 x + r 2 只有一個(gè)重根x，則數(shù)列的顯式通項(xiàng)公式是:an=c1xn+c2 xn其中常數(shù)c1,c2 由初始條件確定。證明 .an =c1 x1n+c2x2n = c1x1n-2 x12+c2x2n-2x2 2= c1x1n-2 (r 1x1+r 2)+ c2x2n-2(r 1x2+r 2)n-1n-2n-1n-2

25、= r 1 c1 x1 +r 2 c1x1+r 1 c2x2+r 2 c2x2= r 1 (c1x1 n-1+ c2x2 n-1 ) +r 2(c1x1n-2 + c2x2n-2)= r 1 an-1+r 2an-2例 7求遞推關(guān)系 an = 3an-1 - 2an-2 ，a1=5, a2=3 的顯式通項(xiàng)公式。解 . 特征方程 x2=3x-2 的兩個(gè)根是 1 和 2。an =c1 1n+c22nc1 +2c2=5c1 +4c2=3c1=7,c2=-1由此得到an =7-2n例 9求 Fibonacci Sequence 菲波納奇數(shù)列的通項(xiàng)公式。Fibonacci Sequence的遞推公式 :

26、fn=fn-1+fn-2,f1 =f2=12解Fibonacci Sequence的特征方程x -x-1=0x =15,15x =1222由定理 1,Fibonacci Sequence的通項(xiàng)公式 :fn=c1 x1n+c2 x2n115215=1c2+c2152+c215c122c1=1c2=155n1fn = 115255n例 10證明 fn5.<3Proof. (by strong induction)P(n):fn<(a) P(1):1<5/3true5i(b)Assumei<kP(i):fi<3Weshow that P(k) is true:2=1n1

27、 52n5.3k1k 2k2k555551 <fk= fk-1 +fk-2<+=3.3333The induction is finished completely.錯(cuò)位排列 alternate permutation14A=1,2,3,42143234124133412314234214312412343212 A=1,2,n A A A k k k=1,2, ,n.DnnD1=0,D2=1, D3=2, D4=9,k1,n-1kk1,n-2Dn-2k k 1, n-1 Dn-1Dn=(n-1)(Dn-2+Dn-1)DnnDn-1=(n-1)Dn-2 Dn-1= (Dn-1(n-1)Dn-2)=( 1)2 (Dn-2(n-2)Dn-3)=n-2=( 1)(D22D1)n-2Dn =nDn-1+( 1)D4=4 2+1=9DnAiii|Ai |=(n-1)!|Ai A j | (n-2)!|Ai A j A k |(n-3)!Dn= | A1A2An | =|A| | A1A2An |=|A|-| Ai |+| Ai A j |+ 1 n | A1An |=n!-C n1(n-1)!+ Cn2 (n2)!- +(1) n C nn= n! (1111( 1)n 1 )1!2!3!n!禁位排列 forbidedpermiti