1、組合數(shù)學(xué),北京科技大學(xué) 唐思銘,前言,組合數(shù)學(xué)是一個(gè)古老而又年輕的數(shù)學(xué)分支。 據(jù)傳說(shuō)，大禹在4000多年前就觀察到神龜背上的幻方.,前言,幻方可以看作是一個(gè)3階方陣，其元素是1到9的正整數(shù)，每行、每列以及兩條對(duì)角線的和都是15。,5,1,9,3,7,2,4,8,6,前言,賈憲 北宋數(shù)學(xué)家（約11世紀(jì)） 著有黃帝九章細(xì)草、算法斅古集斅 音“笑（“古算法導(dǎo)引”）都已失傳。楊輝著詳解九章算法（1261年）中曾引賈憲的“開方作法本源”圖（即指數(shù)為正整數(shù)的二項(xiàng)式展開系數(shù)表，現(xiàn)稱“楊輝三角形”）和“增乘開方法”（求高次冪的正根法）。前者比帕斯卡三角形早600年，后者比霍納（William Geoge Ho

2、rner，17861837）的方法（1819年）早770年。,前言,1666年萊布尼茲所著組合學(xué)論文一書問(wèn)世，這是組合數(shù)學(xué)的第一部專著。書中首次使用了組合論（Combinatorics）一詞。,前言,組合數(shù)學(xué)的蓬勃發(fā)展則是在計(jì)算機(jī)問(wèn)世和普遍應(yīng)用之后。由于組合數(shù)學(xué)涉及面廣，內(nèi)容龐雜，并且仍在很快地發(fā)展著，因而還沒有一個(gè)統(tǒng)一而有效的理論體系。這與數(shù)學(xué)分析形成了對(duì)照。,前言,本學(xué)期主要講組合分析（計(jì)數(shù)和枚舉）以及組合優(yōu)化的一部分（線性規(guī)劃的單純形解法）。 組合分析是組合算法的基礎(chǔ)。,前言,組合數(shù)學(xué)經(jīng)常使用的方法并不高深復(fù)雜。最主要的方法是計(jì)數(shù)時(shí)的合理分類和組合模型的轉(zhuǎn)換。 但是，要學(xué)好組合數(shù)學(xué)并非易

3、事，既需要一定的數(shù)學(xué)修養(yǎng)，也要進(jìn)行相當(dāng)?shù)挠?xùn)練。,第一章排列組合,1.1 加法法則與乘法法則,1.1 加法法則與乘法法則, 加法法則 設(shè)事件A有m種產(chǎn)生方式， 事件B有n種產(chǎn)生方式，則事件A或B之一 有m+n種產(chǎn)生方式。,集合論語(yǔ)言： 若 |A| = m , |B| = n , AB = , 則 |AB| = m + n 。,1.1 加法法則與乘法法則, 例 某班選修企業(yè)管理的有 18 人，不選 的有 10 人，則該班共有 18 + 10 = 28 人。, 例 北京每天直達(dá)上海的客車有 5 次，客 機(jī)有 3 次， 則每天由北京直達(dá)上海的旅行 方式有 5 + 3 = 8 種。,1.1 加法法則與乘

4、法法則, 乘法法則 設(shè)事件A有m種產(chǎn)生式，事件B有n種產(chǎn)生方式，則事件A與B有 m n種產(chǎn)生方式。,集合論語(yǔ)言： 若 |A| = m , |B| = n , AB = (a,b) | a A,b B, 則 |A B| = m n 。,1.1 加法法則與乘法法則,例 某種字符串由兩個(gè)字符組成，第一個(gè)字符可選自a，b，c，d，e，第二個(gè)字符可選自1，2，3，則這種字符串共有5 3 = 15 個(gè)。,例 從A到B有三條道路，從B到C有兩條道路，則從A經(jīng)B到C有32=6 條道路。,1.1 加法法則與乘法法則,例 某種樣式的運(yùn)動(dòng)服的著色由底色和裝飾條紋的顏色配成。底色可選紅、藍(lán)、橙、黃，條紋色可選黑、白，

5、則共有42 = 8種著色方案。 若此例改成底色和條紋都用紅、藍(lán)、橙、黃四種顏色的話，則，方案數(shù)就不是4 4 = 16， 而只有 4 3 = 12 種。 在乘法法則中要注意事件 A 和 事件 B 的相互獨(dú)立性。,1.1 加法法則與乘法法則,例 1)求小于10000的含1的正整數(shù)的個(gè)數(shù) 2)求小于10000的含0的正整數(shù)的個(gè)數(shù),1)小于10000的不含1的正整數(shù)可看做4位數(shù), 但0000除外. 故有999916560個(gè). 含1的有：99996560=3439個(gè),另: 全部4位數(shù)有10 個(gè),不含1的四位數(shù)有9 個(gè), 含1的4位數(shù)為兩個(gè)的差: 10 9 = 3439個(gè),4 4,4 4,2)“含0”和“

6、含1”不可直接套用。0019 含1但不含0。 在組合的習(xí)題中有許多類似的隱含的 規(guī)定，要特別留神。,不含0的1位數(shù)有9個(gè)，2位數(shù)有9 個(gè)， 3位數(shù)有9 個(gè)，4位數(shù)有9 個(gè),不含0小于10000的正整數(shù)有 9+9 +9 +9 =(9 1)/(91)=7380個(gè),含0小于10000的正整數(shù)有 99997380=2619個(gè),2,3,4,2,3,4,5,1.2排列與組合,定義 從n個(gè)不同的元素中，取r個(gè)不重復(fù)的元素，按次序排列，稱為從n個(gè)中取r個(gè)的無(wú)重排列。排列的全體組成的集合用P(n,r)表示。排列的個(gè)數(shù)用P(n,r)表示。當(dāng)r=n時(shí)稱為全排列。一般不說(shuō)可重即無(wú)重?？芍嘏帕械南鄳?yīng)記號(hào)為 - P(n,

7、r),P(n,r)。,1.2排列與組合,定義從n個(gè)不同元素中取r個(gè)不重復(fù)的元素組成一個(gè)子集，而不考慮其元素的順序，稱為從n個(gè)中取r個(gè)的無(wú)重組合。 組合的全體組成的集合用C(n,r)表示，組合的個(gè)數(shù)用C(n,r)表示，對(duì)應(yīng)于可重組合 - 有記號(hào)C(n,r),C(n,r)。,1.2排列與組合,從n個(gè)中取r個(gè)的排列的典型例子是從n個(gè)不同的球中,取出r個(gè),放入r個(gè)不同的盒子里,每盒1個(gè)。第1個(gè)盒子有n種選擇，第2個(gè)有n-1種選擇，第r個(gè)有n-r+1種選擇。 故有 P(n,r)=n(n-1)(n-r+1) 有時(shí)也用nr記n(n-1)(n-r+1),1.2排列與組合,若球不同，盒子相同，則是從n個(gè)中取r個(gè)

8、的組合的模型。若放入盒子后再將盒子標(biāo)號(hào)區(qū)別，則又回到排列模型。每一個(gè)組合可有r!個(gè)標(biāo)號(hào)方案。 故有 C(n,r)r!=P(n,r), C(n,r)=P(n,r)/r!=nr/r!=( )= 易見 P(n,r)=n,n r,r,n! r!(n-r)!,1.2排列與組合,例 有5本不同的日文書，7本不同的英文書，10本不同的中文書。 1)取2本不同文字的書； 2)取2本相同文字的書； 3)任取兩本書,1.2排列與組合,5+7+10 2,解 1) 57+510+710=155; 2) C(5,2)+C(7,2)+C(10,2) =10+21+45=76; 3) 155+76=231=( ),1.2排

9、列與組合,求r1個(gè)1，r2個(gè)2，rt個(gè)t的排列數(shù)，設(shè)r1+r2+rt=n,設(shè)此排列數(shù)為P(n;r1,r2,rt),對(duì)1，2，t分別加下標(biāo)，得到 P(n；r1,r2,rt)r1!r2!rt! = n! P(n；r1,r2,rt)= =( ),n! r1!r2!rt!,n r1 r2 rt,1.2排列與組合,從n個(gè)中取r個(gè)的圓排列的排列數(shù)為 P(n,r)/r , 2rn 以4個(gè)元素為例,1 2 4 3 1234,1 2 4 3 2341,1 2 4 3 3412,1 2 4 3 4123,1.2排列與組合,從n個(gè)中取r個(gè)的項(xiàng)鏈排列的排列數(shù)為 P(n,r)/2r, 3rn 項(xiàng)鏈排列就是說(shuō)排列的方法和

10、項(xiàng)鏈一樣,在圓排列的基礎(chǔ)上，正面向上和反面向上兩種方式放置各個(gè)數(shù)是同一個(gè)排列。 例 下面兩種方式實(shí)際上表示的都是3個(gè)元素的同一種排列。,1 1 2 3 3 2,1.2排列與組合,例 從1,300中取3個(gè)不同的數(shù)，使這3個(gè)數(shù)的和能被3整除，有多少種方案？,解 將1,300分成3類： A=i|i1(mod 3)=1,4,7,298, B=i|i2(mod 3)=2,5,8,299, C=i|i3(mod 3)=3,6,9,300. 要滿足條件，有四種解法： 1)3個(gè)數(shù)同屬于A;2)3個(gè)數(shù)同屬于B 3)3個(gè)數(shù)同屬于C;4)A,B,C各取一數(shù).,故共有3C(100,3)+100 =485100+100

11、0000=1485100,3,1.2排列與組合,例 某車站有6個(gè)入口處，每個(gè)入口處每次只能進(jìn)一人，一組9個(gè)人進(jìn)站的方案有多少？,解一進(jìn)站方案表示成：00011001010100 其中“0”表示人，“1”表示門框，其中“0”是 不同元，“1”是相同元。給“1”n個(gè)門只用n-1 個(gè)門框。任意進(jìn)站方案可表示成上面14個(gè) 元素的一個(gè)排列。,1.2排列與組合,解法1標(biāo)號(hào)可產(chǎn)生5!個(gè)14個(gè)元的全排列。 故若設(shè)x為所求方案，則 x5!=14! x=14!/5!=726485760,1.2排列與組合,解法2在14個(gè)元的排列中先確定“1”的位置，有C(14,5)種選擇，在確定人的位置，有9！種選擇。 故C(14

12、,5)9!即所求,1.2排列與組合,解法3把全部選擇分解成若干步，使每步宜于計(jì)算。不妨設(shè)9個(gè)人編成1至9號(hào)。1號(hào)有6種選擇；2號(hào)除可有1號(hào)的所有選擇外，還可（也必須）選擇當(dāng)與1號(hào)同一門時(shí)在1號(hào)的前面還是后面，故2號(hào)有7種選擇；3號(hào)的選擇方法同2號(hào)，故共有8種。 以此類推，9號(hào)有14種選擇。 故所求方案為6*7*8*14=14!/5!,1.3 Stirling近似公式,組合計(jì)數(shù)的漸進(jìn)值問(wèn)題是組合論的一個(gè)研究方向。 Stirling公式給出一個(gè)求n!的近似公式，它對(duì)從事計(jì)算和理論分析都是有意義的。,1.3 Stirling近似公式,1)Wallis公式,令I(lǐng)k= sin xdx.顯然I0= ,I1

13、=1. k2時(shí)， Ik=cosxsin x| + (k1)cos xsin xdx =0+(k1) (1sin x)sin xdx =(k1)(Ik2Ik),k, 2,k-1, 2 0, 2 0, 2 0, 2 0,2 k-2,2 k-2,故 Ik = Ik-2 (1-3-1),k-1 k,1.3 Stirling近似公式,令n! =,135(n-2)n，n是奇數(shù)。 246(n-2)n，n是偶數(shù)。,(1-3-2),由(1-3-1)， I1, k是奇數(shù) Ik= I0, k是偶數(shù),(k-1)! k! (k-1)! k!,當(dāng)x(0,/2)時(shí)， sin x sin x 因而 I2k+1I2kI2k-1

14、, k=1,2,。,k+1 k,1.3 Stirling近似公式,由(1-3-2), ，,(2k)! (2k-1)! (2k-2)! (2k+1)! (2k)! 2 (2k-1)!,1 1., 2,(2k)! (2k-1)!,1 2k+1,2k+1 2k,2,k,1.3 Stirling近似公式,所以,lim = ,(2k)! (2k-1)!,1 2k+1,2, 2,k,lim = ,(2k)!(2k)! (2k)!,1 2k+1,2, 2,k,lim = 。(1-10-3),2 (k!) (2k)!,1 2k+1,2, 2,k,2k 2,1.3 Stirling近似公式,2)stirling

15、公式,y y=lnx 0 1 2 3 n-1 n x,1.3 Stirling近似公式,令A(yù)n=lnxdx=xlnx| dx=nlnnn+1 (1-3-4) tn=ln1+ln2+ln(n1)+lnn=ln(n!)lnn (1-3-5) tn的幾何意義是由x軸,x=n,以及連接(1,0), (2,ln2),(n1,ln(n1),(n,lnn)諸點(diǎn)而成的折線圍成的面積。,n n n 1 1 1,1 1 2 2,1 2,1.3 Stirling近似公式,Tn=+ln2+ln(n1)+lnn (1-3-6),1 1 8 2,Tn是由三部分面積之和構(gòu)成的。一是曲線 y=lnx在x=k點(diǎn)的切線和x軸，以

16、及x=k, x=k包圍的梯形，當(dāng)k分別為2,3,n-1 時(shí)的面積之和；一是由y=lnx在x=1點(diǎn)的切 線，x=3/2線，以及x軸圍城的梯形；另一 是由y=lnn,x=n,x=n及x軸包圍的矩形 面積。因而有 tnAnTn (1-3-7),1 2,1 2,1 2,1.3 Stirling近似公式,令bn=An tn.序列b1,b2,是單調(diào)增，而且有上界，故有極限，令 limbn=b1 由(1-3-4),(1-3-5) 得 bn=nlnnn+1ln(n!)+lnn = lnnn+1ln(n!)+ln n ln(n!)=1bn+ lnn ln n lne n!=e n ()(1-3-8),0Antn

17、Tntn=,1 8,n,1 2,n,n n,1-bn,n e,n,1 2,1.3 Stirling近似公式,令n=e ,limn=. 將(1-3-8)代入(1-3-3),整理得 = 2 . 所以n! 2n (),n,1-bn,n e,n,1.4模型轉(zhuǎn)換,“一一對(duì)應(yīng)”概念是一個(gè)在計(jì)數(shù)中極為基本的概念。一一對(duì)應(yīng)既是單射又是滿射。 如我們說(shuō)A集合有n個(gè)元素 |A|=n，無(wú)非是建立了將A中元與1,n元一一對(duì)應(yīng)的關(guān)系。 在組合計(jì)數(shù)時(shí)往往借助于一一對(duì)應(yīng)實(shí)現(xiàn)模型轉(zhuǎn)換。 比如要對(duì)A集合計(jì)數(shù)，但直接計(jì)數(shù)有困難，于是可設(shè)法構(gòu)造一易于計(jì)數(shù)的B，使得A與B一一對(duì)應(yīng)。,1.4模型轉(zhuǎn)換,例,簡(jiǎn)單格路問(wèn)題 |(0,0)(m

18、,n)|=( ) 從 (0,0)點(diǎn)出發(fā)沿x軸或y軸的正方向每步 走一個(gè)單位，最終走到(m,n)點(diǎn)，有多少 條路徑？,m+n m,y (m,n) . . . 0 . . . x,1.4模型轉(zhuǎn)換,無(wú)論怎樣走法，在x方向上總共走m步，在y方向上總共走n步。若用一個(gè)x表示x方向上的一步，一個(gè)字母y表示y方向上的一步。 則(0,0)(m,n)的每一條路徑可表示為m 個(gè)x與n個(gè)y的一個(gè)有重排列。將每一個(gè)有重排列的x與y分別編號(hào)，可得m!n!個(gè)m+n元的無(wú)重全排列。,1.4模型轉(zhuǎn)換,設(shè)所求方案數(shù)為p(m+n；m，n) 則P(m+n；m，n)m!n!=(m+n)! 故P(m+n;m,n)= = ( ) =(

19、) =C(m+n,m) 設(shè)ca,db,則由(a,b)到(c,d)的簡(jiǎn)單格路數(shù)為|(a,b)(c,d)|=( ),(m+n)! m+n m+n m!n! m n,(c-a)+(d-b) c-a,(c,d) (a,b),1.4模型轉(zhuǎn)換,例 在上例的基礎(chǔ)上若設(shè)mn，求(0,1)點(diǎn)到(m,n)點(diǎn)不接觸對(duì)角線x=y的格路的數(shù)目 (“接觸”包括“穿過(guò)”) 從(0,1)點(diǎn)到(m,n)點(diǎn)的格路，有的接觸x=y，有的不接觸。 對(duì)每一條接觸x=y的格路，做(0,1)點(diǎn)到第一個(gè)接觸點(diǎn)部分關(guān)于x=y的對(duì)稱格路，這樣得到一條從(1,0)到(m,n)的格路。,1.4模型轉(zhuǎn)換,容易看出從(0,1)到(m,n)接觸x=y的格

20、路與 (1,0)到(m,n)的格路(必穿過(guò)x=y)一一對(duì)應(yīng),y y=x (m,n) 0 (1,0) x,(0,1),. .,y x-y=1 (m,n) x,(0,0) (1,-1),. . . .,.,1.4模型轉(zhuǎn)換,故所求格路數(shù)為( )( ) = = ( ) = ( )=(1 )( ) = ( ),m+n-1 m+n-1 m m-1,(m+n-1)! (m+n-1)! (m+n-1)! 1 1 m!(n-1)! (m-1)!n! (m-1)!(n-1)! m n,m+n-1 m+n-1 m m,n-m m n n,m+n-1 m,n-m n,1.4模型轉(zhuǎn)換,若條件改為可接觸但不可穿過(guò)，則限制

21、線要向下或向右移一格，得xy=1，(0,0)關(guān)于xy=1的對(duì)稱點(diǎn)為(1,-1). 所求格路數(shù)為 ( )( ) = = ( ),m+n m+n m m-1,(m+n)! (m+n)! n+1-m m!n! (m-1)!(n+1)! n+1,m+n m,格路也是一種常用模型,1.4模型轉(zhuǎn)換,例 CnH2n+2是碳?xì)浠衔?隨著n的不同有下列不同的枝鏈：,H | H C H | H,H | H C H | H C H | H,H | H C H | H C H | H C H | H,n=1甲烷 n=2 乙烷 n=3 丙烷,1.4模型轉(zhuǎn)換,H | H C H | H C H | H C H | H

22、C H | H,H | H H C H | | H C C H | | H C H | H H,n=4 丁烷 n=4異丁烷,這說(shuō)明對(duì)應(yīng)CnH2n+2的 枝鏈?zhǔn)怯?n+2個(gè)頂點(diǎn)的一棵樹，其中n個(gè)頂點(diǎn)與之關(guān)聯(lián)的邊數(shù)為4；其它2n+2個(gè)頂點(diǎn)是葉子。對(duì)于這樣結(jié)構(gòu)的每一棵樹，就對(duì)應(yīng)有一種特定的化,合物。從而可以通過(guò)研究具有上述性質(zhì)的 樹找到不同的碳?xì)浠衔顲nH2n+2.,1.4模型轉(zhuǎn)換,例 在100名選手之間進(jìn)行淘汰賽(即一場(chǎng)的比賽結(jié)果，失敗者退出比賽),最后產(chǎn)生一名冠軍，問(wèn)要舉行幾場(chǎng)比賽？ 解 一種常見的思路是按輪計(jì)場(chǎng)，費(fèi)事。另一種思路是淘汰的選手與比賽(按場(chǎng)計(jì))集一一對(duì)應(yīng)。99場(chǎng)比賽。,1.4模型

23、轉(zhuǎn)換,例 (Cayley定理) n個(gè)有標(biāo)號(hào)的頂點(diǎn)的樹的數(shù)目等于n 。,n-2,生長(zhǎng)點(diǎn)不是葉子,每個(gè)生長(zhǎng)點(diǎn)是1,n中的 任一元.有n種選擇。兩個(gè)頂點(diǎn)的樹是唯一的。,1.4模型轉(zhuǎn)換, | | ,4 1 2 5 3,逐個(gè)摘去標(biāo)號(hào)最小的葉子，葉子的相鄰 頂點(diǎn)(不是葉子，是內(nèi)點(diǎn))形成一個(gè)序列， 序列的長(zhǎng)度為n-2,例,給定一棵有標(biāo)號(hào)的樹,邊上的標(biāo)號(hào)表示摘去葉 的順序。(摘去一個(gè)葉子 相應(yīng)去掉一條邊),第一次摘掉，為相鄰的頂點(diǎn)， 得到序列的第一個(gè)數(shù)3,以此類推，得到序列31551,長(zhǎng)度為72 = 5 這是由樹形成序列的過(guò)程。,1.4模型轉(zhuǎn)換,由序列形成樹的過(guò)程：,由序列31551得到一個(gè)新序列111233

24、455567,生成的過(guò)程是首先將31551排序得到11355， 因?yàn)樾蛄?1551的長(zhǎng)度為5，得到按升序排序 的序列1234567，序列的長(zhǎng)度為5+2(即n+2)， 然后將11355按照大小插入到序列1234567中， 得到111233455567,然后將兩個(gè)序列排在一起,31551 111233455567,1.4模型轉(zhuǎn)換,31551 111233455567,1551 1113455567,551 11455567,51 115567,1 1157,17,第一步推導(dǎo)：將上下兩個(gè)序列同時(shí)去掉上 行序列的第一個(gè)元素3(用黃色表示)，去掉 下行序列的第一個(gè)無(wú)重復(fù)的元素2(用紅色 表示)。生成一條

25、邊()。,依此類推，減到下面剩最后兩個(gè)元素，這 兩個(gè)元素形成最后一條邊。最后形成樹。,1.4模型轉(zhuǎn)換,上述算法描述：,給定序列b=(b1b2bn-2) 設(shè)a=(123n-1 n)將b的 各位插入a,得a,對(duì)( )做操作。 a是2n-2個(gè)元的可重非減序列。,b a,操作是從a中去掉最小無(wú)重元，設(shè)為a1,再?gòu)腷 和a中各去掉一個(gè)b中的第一個(gè)元素，設(shè)為b1， 則無(wú)序?qū)?a1,b1)是一條邊。重復(fù)這一操作，得 n-2條邊，最后a中還剩一條邊，共 n-1條邊， 正好構(gòu)成一個(gè)樹。b中每去掉一個(gè)元，a中去 掉2個(gè)元。,1.4模型轉(zhuǎn)換,由算法知由樹T得b=(b1b2bn-2) ，反之，由b可得T。即 f：Tb

26、 是一一對(duì)應(yīng)。 由序列確定的長(zhǎng)邊過(guò)程是不會(huì)形成回路的。因任意長(zhǎng)出的邊 (u , v) 若屬于某回路，此回路中必有一條最早生成的邊，不妨就設(shè)為 (u , v) ，必須使u,v都在長(zhǎng)出的邊中重復(fù)出現(xiàn)，但照算法u,v之一從下行消失，不妨設(shè)為u，從而不可能再生成與u有關(guān)的邊了，故由( )得到的邊必構(gòu)成一個(gè)n個(gè)頂點(diǎn)的樹。,b a,1.4模型轉(zhuǎn)換,證 由一棵n個(gè)頂點(diǎn)的樹可得到一個(gè)長(zhǎng)度為n2的序列，且不同的樹對(duì)應(yīng)的序列 不同*，因此 | T | n 。 *對(duì)n用歸納法可證 反之，由一個(gè)長(zhǎng)度為n2的序列(每個(gè)元素為1 n 的一個(gè)整數(shù))，可得到一棵樹，且不同的序列對(duì)應(yīng)的樹是不同的，因此 n | T | | T

27、| = n #,n-2,n-2,n-2,1.5全排列的生成算法,就是對(duì)于給定的字符集，用有效的方法將所有可能的全排列無(wú)重復(fù)無(wú)遺漏地枚舉出來(lái)。,全排列的生成算法,1.5全排列的生成算法,這里介紹全排列算法四種：,(A)字典序法 (B)遞增進(jìn)位制數(shù)法 (C)遞減進(jìn)位制數(shù)法 (D)鄰位對(duì)換法,1.5.1字典序法,對(duì)給定的字符集中的字符規(guī)定了一個(gè)先后關(guān)系，在此基礎(chǔ)上規(guī)定兩個(gè)全排列的先后是從左到右逐個(gè)比較對(duì)應(yīng)的字符的先后。,1.5.1字典序法,例字符集1,2,3,較小的數(shù)字較先,這樣按字典序生成的全排列是: 123,132,213,231,312,321。, 一個(gè)全排列可看做一個(gè)字符串，字 符串可有前綴

28、、后綴。,1.5.1字典序法,1）生成給定全排列的下一個(gè)排列 所謂一個(gè)的下一個(gè)就是這一個(gè)與 下一個(gè)之間沒有其他的。這就要求這一個(gè)與下一個(gè)有盡可能長(zhǎng)的共同前綴，也即變化限制在盡可能短的后綴上。,1.5.1字典序法,例 839647521是1-9的排列。19的排列最前面的是123456789，最后面的是987654321，從右向左掃描若都是增的，就到了987654321，也就沒有下 一個(gè)了。否則找出第一次出現(xiàn)下降的位置。,1.5.1字典序法,求839647521的下一個(gè)排列,7 5 2 1,7,47,45,5,42,2,41,1,在后綴7521中找出比4大的數(shù),7 5,找出其中比4大的最小數(shù),5,

29、5,4 、5 對(duì)換,8396 7 21,5,4,后綴變?yōu)?421,將此后綴翻轉(zhuǎn),12 4 7,接上前綴83965得到839651247 即839647521的下一個(gè)。,例,為后綴,大于4的用橙色表示 小于4的用綠色表示,找出比右邊數(shù)字小的第一個(gè)數(shù)4,1.5.1字典序法,在1,n的全排列中,n n-1 321是最后一個(gè)排列,其中介數(shù)是(n-1, n-2,.,3,2,1)其序號(hào)為,n-1 kk! k=1,另一方面可直接看出其序號(hào)為n!-1 n-1 n-1 于是n!-1= kk! 即 n!=kk! +1 k=1 k=1,1.5.1字典序法,一般而言，設(shè)P是1,n的一個(gè)全排列。,P=P1P2Pn=P1

30、P2Pj-1PjPj+1Pk-1PkPk+1Pn j=maxi|PiPj 對(duì)換Pj，Pk，將Pj+1Pk-1PjPk+1Pn翻轉(zhuǎn)， P= P1P2Pj-1PkPnPk+1PjPk-1Pj+1即P的下一個(gè),1.5.1字典序法,2)計(jì)算給定排列的序號(hào),839647521的序號(hào)即先于此排列的排列的個(gè)數(shù)。 將先于此排列的排列按前綴分類。,前綴先于8的排列的個(gè)數(shù)：78!,第一位是8,先于83得的排列的個(gè)數(shù)：27!,前2位是83,先于839得的排列的個(gè)數(shù)：66!,先于此排列的的排列的個(gè)數(shù)：,78!,+27!,+66!,前3位是839,先于8396得的排列的個(gè)數(shù)：45!,+45!,前4位是8396,先于83

31、964得的排列的個(gè)數(shù)：24!,+24!,前5位是83964,先于839647得的排列的個(gè)數(shù)：33!,+33!,前6位是839647,先于8396475得的排列的個(gè)數(shù)：22!,+22!,前7位是8396475,先于83964752得的排列的個(gè)數(shù)：11!,+11!,297191,前8位固定，則最后一位也隨之固定,將8!,7!,1!前面的系數(shù)抽出，放在一起 得到,72642321,此數(shù)的特點(diǎn)：,7：8的右邊比8小的數(shù)的個(gè)數(shù),2：3的右邊比3小的數(shù)的個(gè)數(shù),6：9的右邊比9小的數(shù)的個(gè)數(shù),4：6的右邊比6小的數(shù)的個(gè)數(shù),2：4的右邊比4小的數(shù)的個(gè)數(shù),3：7的右邊比7小的數(shù)的個(gè)數(shù),2：5的右邊比5小的數(shù)的個(gè)數(shù)

32、,1：2的右邊比2小的數(shù)的個(gè)數(shù),72642321是計(jì)算排列839647521的序號(hào)的中間環(huán)節(jié)， 我們稱之為中介數(shù)。 這是一個(gè)很有用的概念。,1.5.1字典序法,一般而言,對(duì)于1,9的全排列中介數(shù)首位的取值為08，第2位的取值為07，以此類推，第8位的取值為0、1。從而序號(hào)可表示為： n-1 ki(n-i)! i=1 ki：Pi的右邊比Pi小的數(shù)的個(gè)數(shù) i=1,2,n-1,1.5.1字典序法,由中介數(shù)推出排列的算法,例 由72642321推算出839647521,方法1：,P1 P2 P3 P4 P5 P6 P7 P8 P9 _ _ _ _ _ _ _ _ _,P1=8,8,7+1=8,2+1=

33、3,P2=3,3,6+1=7，但3已在P3左邊出現(xiàn)，,7+1=8，但8已在P3左邊出現(xiàn)，,8+1=9 P3=9,9,4+1=5，但3已經(jīng)在P4左邊出現(xiàn)， 5+1=6 P4=6,6,2+1=3，但3已經(jīng)在P5左邊出現(xiàn)， 3+1=4 P4=4,4,3+1=4，但3,4已經(jīng)在P6左邊出現(xiàn)， 4+1+1=6，但6已經(jīng)在P6左邊出現(xiàn)， 6+1=7 P6=7,7,2+1=3，但3已經(jīng)在P7左邊出現(xiàn)， 3+1=4，但4已經(jīng)在P7左邊出現(xiàn)， 4+1=5 P7=5,5,1+1=2 P8=2 P9=1,2 1,這個(gè)過(guò)程比較麻煩(這醞釀著改進(jìn)的可能)， 該算法從左到右依次推出P1,P2,P9。 下述算法依次定出1,

34、2,3,9的位置。,1.5.1字典序法,方法2-1：,72642321中未出現(xiàn)0，1在最右邊,中介數(shù)右端加一個(gè)0擴(kuò)成9位，先定1，每定 一位，其左邊未定位下加一點(diǎn)，從（位 位下點(diǎn)數(shù)=0）的位中選最左的。,7 2 6 4 2 3 2 1 0,定 1 的位置,1,2,2,3,3,4,4, ,5,5, ,6,6, ,7,7, ,8,8,9,9,由72642321推算出839647521,1.5.1字典序法,方法2-2：,已定出上標(biāo)，找左起第一個(gè)0，下標(biāo)_,由72642321推算出839647521, 72642321-11111111=61531210,_ _ _ _ _ _ _ _ 1,2, 61

35、531210 -11111110=50420100,3, 50420100 -10000000=40420100,4, 40420100 -10110000=30310100,5, 30310100 -10110100=20200000,6, 20200000 -10100000=10100000,7, 10100000 -10100000=00000000,8, 00000000,9,以上兩種從中介數(shù)求排列的算法都比較麻煩。給定一排列與下一個(gè)排列各自的中介數(shù)進(jìn)位鏈（中介數(shù)的后繼）遞增進(jìn)位制數(shù),1.5.2遞增進(jìn)位制數(shù)法,1)由排列求中介數(shù),在字典序法中，中介數(shù)的各位是由排 列數(shù)的位決定的.中介

36、數(shù)位的下標(biāo)與排列 的位的下標(biāo)一致。,在遞增進(jìn)位制數(shù)法中，中介數(shù)的各位是由排列中的數(shù)字決定的。即中介數(shù)中各位的下標(biāo)與排列中的數(shù)字(2n)一致。,1.5.2遞增進(jìn)位制數(shù)法,可看出n-1位的進(jìn)位鏈。 右端位逢2進(jìn)1，右起第2位逢3進(jìn)1， 右起第i位逢i+1進(jìn)1，i=1,2,n-1. 這樣的中介數(shù)我們稱為遞增進(jìn)位制數(shù)。 上面是由中介數(shù)求排列。,1.5.2遞增進(jìn)位制數(shù)法,由序號(hào)（十進(jìn)制數(shù)）求中介數(shù)（遞增進(jìn)位制數(shù)）如下： m=m1, 0 m n!-1 m1=2m2+kn-1, 0 kn-1 1 m2=3m3+kn-2, 0 kn-2 2 . mn-2=(n-1)mn-1+k2, 0 k2 n-2 mn-1

37、=k1, 0 k1 n-1 p1p2pn(k1k2kn-1) m,1.5.2遞增進(jìn)位制數(shù)法,在字典序法中由中介數(shù)求排列比較麻煩，我們可以通過(guò)另外定義遞增進(jìn)位制數(shù)加以改進(jìn)。,為方便起見，令ai+1=kn-I，i=1,2,n-1 (k1k2kn-1)=(anan-1a2) ai：i的右邊比i小的數(shù)字的個(gè)數(shù),1.5.2遞增進(jìn)位制數(shù)法,在這樣的定義下，有 839647521(67342221) (67342221)+1=(67342300) 849617523 68+7)7+3)6+4)5+2)4+2)3+2)2+1 =279905,1.5.2遞增進(jìn)位制數(shù)法,由(anan-1a2)求p1p2pn。,從

38、大到小求出n,n-1,2,1的位置 _ . _ n _ _ _ an個(gè)空格 n的右邊有an個(gè)空格。 n-1的右邊有an-1個(gè)空格。 2的右邊有a2個(gè)空格。 最后一個(gè)空格就是1的位置。,_ _/ V,1.5.2遞增進(jìn)位制數(shù)法,_ _ _ _ _ _ _ _ _,6 7 3 4 2 2 2 1 a9 a8 a7 a6 a5 a4 a3 a2,_ _/ V 6個(gè)空格,9,_ _/ V 7個(gè)空格,8,_ _/ V 3個(gè)空格,7,6,5,4,3,1,_ _/ V 4個(gè)空格,_ _/ V 2個(gè)空格,1個(gè)空格,序號(hào) n m=ak(k-1)! k=2,2,1.5.3遞減進(jìn)位制數(shù)法,在遞增進(jìn)位制數(shù)法中，中介數(shù)的

39、最低位是逢2進(jìn)1，進(jìn)位頻繁，這是一個(gè)缺點(diǎn)。,把遞增進(jìn)位制數(shù)翻轉(zhuǎn),就得到遞減進(jìn)位制數(shù)。,(anan-1a2)(a2a3an-1an) 839647521 (12224376),n n m=akn!/k!=n!ak/k! k=2 k=2,(12224376) =13+2)4+2)5+2)6+4)7+3)8+7)9+6 =340989 求下一個(gè)排列十分容易,1.5.4鄰位對(duì)換法,遞減進(jìn)位制數(shù)法的中介數(shù)進(jìn)位不頻繁，求下一個(gè)排列在不進(jìn)位的情況下很容易。這就啟發(fā)我們，能不能設(shè)計(jì)一種算法，下一個(gè)排列總是上一個(gè)排列某相鄰兩位對(duì)換得到的。遞減進(jìn)位制數(shù)字的換位是單向的，從右向左，而鄰位對(duì)換法的換位是雙向的。,1.

40、5.4鄰位對(duì)換法,這個(gè)算法可描述如下： 對(duì)1n-1的每一個(gè)偶排列，n從右到左插入n個(gè)空檔(包括兩端)，生成1n的n 個(gè)排列。 對(duì)1n-1的每一個(gè)奇排列，n從左到右插入n個(gè)空檔，生成1n的n個(gè)排列。 對(duì)2,n的每個(gè)數(shù)字都是如此。,1.5.4鄰位對(duì)換法,例,839647521 836947521,解,2的右邊有1個(gè)數(shù)字(奇數(shù))比2小,2上加一個(gè)點(diǎn)。,3的右邊有2個(gè)數(shù)字(偶數(shù))比3小,3上不加點(diǎn)。,4的右邊有2個(gè)數(shù)字(偶數(shù))比4小,4上不加點(diǎn)。,5的右邊有2個(gè)數(shù)字(偶數(shù))比5小,5上不加點(diǎn)。,6的右邊有2個(gè)數(shù)字(偶數(shù))比6小,6上不加點(diǎn)。,7的右邊有3個(gè)數(shù)字(奇數(shù))比7小,7上加一個(gè)點(diǎn)。,8的右邊有

41、7個(gè)數(shù)字(奇數(shù))比8小,8上加一個(gè)點(diǎn)。,18上共有3個(gè)(奇數(shù))點(diǎn)，9上箭頭向右。,P= 839647521 ( ) b2 b3 b4 b5 b6 b7 b8 b9,1,0,1,2,1,3,7,2,2上箭頭向左，2右邊有1個(gè)數(shù)字比2小，b2=1,3上箭頭向右，3左邊有0個(gè)數(shù)字比3小，b3=0,4上箭頭向右，4左邊有1個(gè)數(shù)字比4小，b4=1,5上箭頭向右，5左邊有2個(gè)數(shù)字比5小，b5=2,6上箭頭向右，6左邊有1個(gè)數(shù)字比6小，b6=1,7上箭頭向左，7右邊有3個(gè)數(shù)字比7小，b7=3,8上箭頭向左，8右邊有7個(gè)數(shù)字比8小，b8=7,9上箭頭向右，9左邊有2個(gè)數(shù)字比9小，b9=2,839647521的

42、中介數(shù)為10121372,1.5.4鄰位對(duì)換法,ak(p)：p中1k排列的序號(hào)，ak(p)的奇偶性與1k排列的奇偶性相同。,a9(p)=9a8(p)+b9(p) =9(8a7(p)+b8(p)+b9(p),an(p)，bn(p)簡(jiǎn)寫成an，bn,1.5.4鄰位對(duì)換法,已知(10121372)求排列。,9的位置由b9和a8的奇偶性決定。 a8的奇偶性同b8的奇偶性。 a7的奇偶性同b7+b6的奇偶性。b2=0,1。, b8奇9，b6+b7偶8，b6奇7， b4+b5奇6，b4奇5,1.5.4鄰位對(duì)換法,序號(hào)=13+0)4+1)5+2)6+1)7+3)8+7)9+2 =203393(1012137

43、2),1.5.4鄰位對(duì)換法,1.6組合的生成,設(shè)從1,n中取r元的組合全體為C(n,r). C1C2CrC(n,r).不妨設(shè)C1C2Cr iCi(nr+i), i=1,2,r 令j=maxi|Cinr+i. 則C1C2Cr的下一個(gè)組合為C1C2Cj-1(Cj+1)(Cj+2)(Cj+rj+1) 這等于給C(n,r)的元素建立了字典序。 12r的序號(hào)為0，n-r+1 n-r+2n的序號(hào)為( )1,_ _ n r,1.6組合的生成,例 在C(10,4)中 4679的序號(hào)是 首位小于4的組合的個(gè)數(shù)；首位是4，第2位小于6的組合的個(gè)數(shù)；前2位是46，第3位小于7的組合的個(gè)數(shù)；前3位是467，第4位小于

44、9的組合的個(gè)數(shù)之和。 反之，也可以由序號(hào)求組合。,1.6組合的生成,A(m,l)：1,m的l-組合(或l-子集)。 第1個(gè)組合：1,2,l-1,l. 最后1個(gè)組合：1,2,l-1,m A(n,k)=A(n-1,k)，A(n-1,k-1)n A：將有序集A(或線性表)的順序逆轉(zhuǎn)的有序集。 An：將A中每個(gè)元素(是集合)都與n求并的有序集,_ ,_,_ _,1.6組合的生成,例 用兩種方法計(jì)算1,n的無(wú)重不相鄰組合C(n,r)的計(jì)數(shù)問(wèn)題 解法1 00100100100100 其中不可含11,/ / ,共n位,r個(gè)1, / /,以1結(jié)尾：r-1個(gè)10與n-1-2(r-1)個(gè)0的排列 r-1+n-1-

45、2(r-1)=n-r 這樣的排列有,(n-r)! = (r-1)!(n-2r+1)!,( ),n-r r-1,1.6組合的生成,以0結(jié)尾： r個(gè)10與n-2r個(gè)0的排列 r+n-2r = n-r 這樣的排列有 ( )個(gè) ()+() = ( ) f(a1a2ar) = b1b2br,n-r r,n-r n-r n-r+1 r-1 r r,1.6組合的生成,解法 任給a1a2arC(n,r),a1 a2 ar 令f：a1a2arb1b2br bi = ai-i+1, i= 1,2,r. 1b1 b2 br n-r+1,b1b2brC(n-r+1,r) C(n,r) = C( n-r+1,r),1.

46、7可重組合,C(n,r)的計(jì)數(shù)問(wèn)題相當(dāng)于r相同的球放入n個(gè)互異的盒子，每盒球的數(shù)目不同的方案的計(jì)數(shù)。而后一問(wèn)題又可轉(zhuǎn)換為r個(gè)相同的球與n-1個(gè)相同的盒壁的排列的問(wèn)題。 易知所求計(jì)數(shù)為 = C(n+r-1,r) 即C(n,r)=( )=C(n-1,r)+C(n,r-1) 不含“” 至少含一個(gè)“”,(n-1+r)! r!(n-1)!,n+r-1 r,r個(gè)相同的球 / 001001100 / / n-1個(gè)相同的盒壁,1.7可重組合,另證設(shè)a1a2arC(n,r)1a1a2 arn, 令C(n,r)上的f，使得bi=ai+i-1,i=1,2,r. 則b1b2br滿足1b1b2brn+r-1 b1b2b

47、rC(n+r-1,r) f： a1a2arb1b2br 顯然f是單射，f ：b1b2bra1a2ar,-1,1.7可重組合,ai=bi-i+1, i=1,2,r. a1a2arC(n,r) f是單射C(n,r)C(n+r-1,r) f 是單射 C(n,r)C(n+r-1,r) C(n,r)=C(n+r-1,r) 第二個(gè)證明可說(shuō)一種“拉伸壓縮”技巧。不可謂不巧妙。但仍不如第一證明來(lái)的明快，由此可見組合證明的功效。, ,-1,1.8若干等式及其組合意義,組合意義或組合證明，含意強(qiáng)弱的不同。承認(rèn)組合證明與其他證明有相同的“合法性”。,1.8若干等式及其組合意義,1. C(n,r)=C(n,n-r)

48、(1.7.1) 從1,n去掉一個(gè)r子集，剩下一個(gè)(n-r)子集。由此建立C(n,r)與C(n,n-r)的一個(gè)一一對(duì)應(yīng)。 故C(n,r)=C(n,n-r),1.8若干等式及其組合意義,2. C(n,r)=C(n-1,r)+C(n-1,r-1) (1.7.2) 從1,n取a1,a2,ar.設(shè)1a1a2arn,對(duì)取法分類：a1=1,有C(n-1,r-1)種方案 ，a11,有C(n-1,r)種方案 共有C(n-1,r)+C(n-1,r-1)中方案，故C(n,r)=C(n-1,r)+C(n-1,r-1),1.8若干等式及其組合意義,楊輝三角除了(0,0)點(diǎn)，都滿足此遞推式 0rn,n0r C(n,r)=

49、 1,r = 00,0nr,r0nn0且r0 C(m+n,m)=C(m+n-1,m)+C(m+n-1,m-1) (0,0)(m,n)=(0,0)(m,n-1)(0,0)(m-1,n),(-1) ( ),|r|-1 |n|-1,n+r,nr r!,1.8若干等式及其組合意義,3.( )+( )+( )+( )=( ) (1.7.3) 1可從(7.2)推論，也可做一下組合證明從1,n+r+1取a1a2anan+1，設(shè)a1a2an an+1，可按a1的取值分類：a1=1,2,3,r,r+1. a1=1, a2an+1取自2,n+r+1 有( )種取法,n n+1 n+2 n+r n+r+1 n n

50、n n n+1,n+r n,a1=2, a2an+1取自3,n+r+1 有( )種取法,n+r-1 n, ,a1=r, a2an+1取自r+1,n+r+1 有( )種取法,n+1 n,a1=r+1, a2an+1取自r+2,n+r+1 有( )種取法,n n,也可看做按含1不含1，含2不含2, 含r不含r的不斷分類,1.8若干等式及其組合意義,2從(0,0)到(n+1,r),過(guò)且僅過(guò)一條帶箭頭的邊,而過(guò)這些邊的路徑有(從下到上) ( ),( ),( ) 故有.( )+( )+( )+( )=( ),n n+1 n+r n n n,n n+1 n+2 n+r n+r+1 n n n n n,r

51、(n+1,r) . . . (0,0) n n+1,1.8若干等式及其組合意義,3 可重組合. 1,n+2的C(n+2,r)模型 ( ) 不含1,含1個(gè)1,含2個(gè)1,含r個(gè)1 C( ),C( ),C( ),C( ) ( ), ( ), ( ), ( ),n+r+1 r,n+1 n+1 n+1 n+1 r r-1 r-2 0,n+r n+r-1 n+r-2 n r r-1 r-2 0,1.8若干等式及其組合意義,4. ( )( )=( )( ) (1.7.4) 選政治局,再選常委,n個(gè)中央委員選出l名政治局委員,再?gòu)钠渲羞x出r名常委 選常委,再選非常委政治局委員 兩種選法都無(wú)遺漏,無(wú)重復(fù)地給出可

52、能的方案，應(yīng)該相等。,n l n n-r l r r l-r,1.8若干等式及其組合意義,5. ( )+( )+( )=2 , m0, (1.7.5) 證1(x+y) =()x y ,令x=y=1,得(1.7.5) 組合證1 1,m的所有方案.每一子集都可取k1,m或不取.這樣有2 個(gè)方案.另可有0-子集(空集),1-子集,m-子集. 組合證2 從(0,0)走m步有2 種走法,都落在直線x+y=m上,而到(m,0),(m-1,1),(m-2,2),(2,m-2),(1,m-1),(0,m)各點(diǎn)的走法各有( ),( ),( ),( ),( ),( )種,m m m m 0 1 m,m k m-k

53、,m m k k=0,m,m,m m m m m m 0 1 2 m-2 m-1 m,1.8若干等式及其組合意義,6. 證1,1.8若干等式及其組合意義,證2 在1,n的所有組合中, 含1的組合不含1的組合.有11對(duì)應(yīng)關(guān)系。在任一含1組合及與之對(duì)應(yīng)的不含1組合中，必有一奇數(shù)個(gè)元的組合與一偶數(shù)個(gè)元的組合。將含奇數(shù)個(gè)元的組合做成集，將含偶數(shù)閣元的組合做成另一集。此二集的元數(shù)相等。()=(),n n i i,i奇 i偶,1.8若干等式及其組合意義,7. (1.7.7) 即Vandermonde恒等式 證1 從m個(gè)互異紅球和n個(gè)互異藍(lán)球中取r個(gè)球,按r個(gè)球中紅球的個(gè)數(shù)分類. 組合證法: (0,0)到(

54、m+n-r)點(diǎn)的路徑. (0,0)(m-r+l,r-l)(m+n-r,r) () ( ) ( )=( )( ),m n r-l l,m+n m n r r-l l,P(m-r,r) (m+n-r,r) (m-r+l,r-l) l=0,1,2,r Q(m,0),r l=0,1.8若干等式及其組合意義,李善蘭(18111882），清代數(shù)學(xué)家 李善蘭恒等式：( )( )( )=( )( ),k l n+k+l-j n+k n+l j j k+l k l,j0,證：利用Vandermonde恒等式及 ( )( )=( )( )=( )( ) (接下頁(yè)),n v n n-p n n-p v p p n-v p v-p,1.8若干等式及其組合意義,有 ( )( )( ) =( )( )( )( ) ) =( )( )( )( ) =( )( )( )( ) =( )( )( ) =( )( )( ) =( )( )( ) =( )( ),k l n+k+l-j j j k+l,k l n+k l-j j j k+v l-v,