1、組合數(shù)學(xué),李清勇 200789,前言,組合數(shù)學(xué)經(jīng)常使用的方法并不高深復(fù)雜。最主要的方法是計數(shù)時的合理分類和組合模型的轉(zhuǎn)換。 但是，要學(xué)好組合數(shù)學(xué)并非易事，既需要一定的數(shù)學(xué)修養(yǎng)，也要進行相當(dāng)?shù)挠?xùn)練。,排列組合,加法法則與乘法法則,排列與組合,模型轉(zhuǎn)換,加法法則與乘法法則, 加法法則 設(shè)事件A有m種產(chǎn)生方式， 事件B有n種產(chǎn)生方式，則事件A或B之一 有m+n種產(chǎn)生方式。,集合論語言： 若 |A| = m , |B| = n , AB = , 則 |AB| = m + n 。,加法法則與乘法法則, 例 某班選修企業(yè)管理的有 18 人，不選 的有 10 人，則該班共有 18 + 10 = 28 人。,

2、 例 北京每天直達上海的客車有 5 次，客機有 3 次， 則每天由北京直達上海的旅行方式有 5 + 3 = 8 種。,加法法則與乘法法則, 乘法法則 設(shè)事件A有m種產(chǎn)生式，事件B有n種產(chǎn)生方式，則事件A與B有 m n種產(chǎn)生方式。,集合論語言： 若 |A| = m , |B| = n , AB = (a,b) | a A,b B, 則 |A B| = m n 。,加法法則與乘法法則,例 某種字符串由兩個字符組成，第一個字符可選自a，b，c，d，e，第二個字符可選自1，2，3，則這種字符串共有5 3 = 15 個。,例 從A到B有三條道路，從B到C有兩條道路，則從A經(jīng)B到C有32=6 條道路。,加

3、法法則與乘法法則,例 某種樣式的運動服的著色由底色和裝飾條紋的顏色配成。底色可選紅、藍、橙、黃，條紋色可選黑、白，則共有42 = 8種著色方案。 若改成底色和條紋都用紅、藍、橙、黃四種顏色?,在乘法法則中要注意事件 A 和 事件 B 的相互獨立性。 加法法則對事件分類計數(shù)，乘法法則對事件分步計數(shù)。,方案數(shù)就不是4 4 = 16， 而只有 4 3 = 12 種。,排列與組合,從n個不同的元素中，取r個不重復(fù)的元素，按次序排列，稱為從n個中取r個的無重排列。排列的全體組成的集合用 P(n,r)表示。排列的個數(shù)用P(n,r)表示。當(dāng)r=n時稱為全排列。一般不說可重即無重。,定義從n個不同元素中取r個

4、不重復(fù)的元素組成一個子集，而不考慮其元素的順序，稱為從n個中取r個的無重組合。組合的全體組成的集合用C(n,r)表示，組合的個數(shù)用C(n,r)表示。,排列與組合,從n個中取r個的排列的典型例子是從n個不同的球中,取出r個,放入r個不同的盒子里,每盒1個。第1個盒子有n種選擇，第2個有n-1種選擇，第r個有n-r+1種選擇。故有 P(n,r)=n(n-1)(n-r+1) 有時也用nr記n(n-1)(n-r+1),排列與組合,若球不同，盒子相同，則是從n個中取r個的組合模型。若放入盒子后再將盒子標(biāo)號區(qū)別，則又回到排列模型。每一個組合可有r!個標(biāo)號方案。故有 C(n,r)r!=P(n,r), C(n

5、,r)=( )=,n r,n! r!(n-r)!,排列與組合,例 有5本不同的日文書，7本不同的英文書，10本不同的中文書。 1)取2本不同文字的書； 2)取2本相同文字的書； 3)任取兩本書,排列與組合,解 1) 57+510+710=155; 2) C(5,2)+C(7,2)+C(10,2) =10+21+45=76; 3) 155+76=231=( ),5+7+10 2,排列與組合,例 從1,300中取3個不同的數(shù)，使這3個數(shù)的和能被3整除，有多少種方案？,解 將1,300分成3類： A=i|i1(mod 3)=1,4,7,298, B=i|i2(mod 3)=2,5,8,299, C=

6、i|i3(mod 3)=3,6,9,300. 要滿足條件，有四種解法： 1)3個數(shù)同屬于A;2)3個數(shù)同屬于B 3)3個數(shù)同屬于C;4)A,B,C各取一數(shù).,故共有3C(100,3)+100 =485100+1000000=1485100,3,模型轉(zhuǎn)換,“一一對應(yīng)”概念是一個在計數(shù)中極為基本的概念。一一對應(yīng)既是單射又是滿射。 如我們說A集合有n個元素 |A|=n，無非是建立了將A中元與1,n元一一對應(yīng)的關(guān)系。 在組合計數(shù)時往往借助于一一對應(yīng)實現(xiàn)模型轉(zhuǎn)換。 比如要對A集合計數(shù)，但直接計數(shù)有困難，于是可設(shè)法構(gòu)造一易于計數(shù)的B，使得A與B一一對應(yīng)。,模型轉(zhuǎn)換,例 在100名選手之間進行淘汰賽(即一場

7、的比賽結(jié)果，失敗者退出比賽),最后產(chǎn)生一名冠軍，問要舉行幾場比賽？ 解 一種常見的思路是按輪計場，費事。另一種思路是淘汰的選手與比賽(按場計)集一一對應(yīng)。99場比賽。,模型轉(zhuǎn)換,簡單格路問題 |(0,0)(m,n)| 從 (0,0)點出發(fā)沿x軸或y軸的正方向每步走一個單位，最終走到(m,n)點，有多少條路徑？,y (m,n) . . . 0 . . . x,模型轉(zhuǎn)換,無論怎樣走法，在x方向上總共走m步，在y方向上總共走n步。若用一個0表示x方向上的一步，一個字母1表示y方向上的一步。 則(0,0)(m,n)的每一條路徑可轉(zhuǎn)換為m 個0與n個1組成的序列。一一映射 這樣的0和1組成的序列的數(shù)目為

8、（ ）,m+n m,全排列的生成算法,就是對于給定的字符集，用有效的方法將所有可能的全排列無重復(fù)無遺漏地枚舉出來。,全排列的生成算法,遞歸方法,令E= e1 , ., en 表示n 個元素的集合，我們的目標(biāo)是生成該集合的所有排列方式。令Ei 為E中移去元素i 以后所獲得的集合，perm (X) 表示集合X 中元素的排列方式，ei.p e r m(X)表示在perm (X) 中的每個排列方式的前面均加上ei 以后所得到的排列方式。例如，如果E=a, b, c，那么E1=b, c，perm (E1 )=( b c, c b)，e1 .perm(E1) = (a b c, a c b)。 對于遞歸的

9、基本部分，采用n = 1。當(dāng)只有一個元素時，只可能產(chǎn)生一種排列方式，所以 perm (E) = (e)，其中e 是E 中的唯一元素。 當(dāng)n 1時，perm (E) = e1 .perm(E1) +e2 .p e r m(E2) +e3.perm(E3) + . +en .perm (En)。這種遞歸定義形式是采用n 個perm(X) 來定義perm(E), 其中每個X 包含n-1個元素。,遞歸方法,void Perm(char *List, int m, int k) /List中保存排列的元素，m表示待排列元素的開始位置，k表示結(jié)束位置。 if(m=k) / 得到一個排列 else for(

10、int i=m; i=k; i+) Swap(Listm,Listi); Perm(List, m+1, k); Swap(Listm,Listi); ,字典序方法,生成給定全排列的下一個排列所謂一個的下一個就是這一個與 下一個之間沒有其他的。這就要求這一個與下一個有盡可能長的共同前綴，也即變化限制在盡可能短的后綴上。 例 839647521是1-9的排列。19的排列最前面的是123456789，最后面的是987654321，從右向左掃描若都是增的，就到了987654321，也就沒有下 一個了。否則找出第一次出現(xiàn)下降的位置。,對給定的字符集中的字符規(guī)定了一個先后關(guān)系，在此基礎(chǔ)上規(guī)定兩個全排列的

11、先后是從左到右逐個比較對應(yīng)的字符的先后。 例字符集1,2,3,較小的數(shù)字較先,這樣按字典序生成的全排列是: 123,132,213,231,312,321。,字典序方法,由一個排列p1p2.pn生成下一個排列的算法： a) i=maxj|pj-1pj,j=2,3,.,n b) j=maxk|pi-1pk,k=1,2,.,n c) pi-1與pj互換 d) pi,pi+1,.,pn逆轉(zhuǎn)，即變成pn,pn-1,.,pi,其它的不變,例 求839647521的下一個排列 i=6; j=8; 互換i和j得到 839657421； 把第6個元素后的子串逆轉(zhuǎn)得到 839651247,若干等式及其組合意義,

12、組合意義或組合證明，含意強弱的不同。承認組合證明與其他證明有相同的“合法性”。,若干等式及其組合意義,1. C(n,r)=C(n,n-r) (1) 從1,n去掉一個r子集，剩下一個(n-r)子集。由此建立C(n,r)與C(n,n-r)的一個一一對應(yīng)。 故C(n,r)=C(n,n-r),若干等式及其組合意義,2. C(n,r)=C(n-1,r)+C(n-1,r-1) (2) 從1,n取a1,a2,ar.設(shè)1a1a2arn,對取法分類：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

13、-1,r-1),若干等式及其組合意義,楊輝三角除了(0,0)點，都滿足此遞推式 0rn,n0r C(n,r)= 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!,若干等式及其組合意義,3.( )+( )+( )+( )=( ) (3) 1 組合證明從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+

14、1 有( )種取法,n n+1 n+2 n+r n+r+1 n n 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的不斷分類,若干等式及其組合意義,2從(0,0)到(n+1,r),過且僅過一條帶箭頭的邊,而過這些邊的路徑有(從下到上) ( ),( ),( ) 故有.( )+( )+( )+( )=( ),n n+1 n+r n n n,n

15、 n+1 n+2 n+r n+r+1 n n n n n,r (n+1,r) . . . (0,0) n n+1,若干等式及其組合意義,4. ( )( )=( )( ) (4) 選政治局,再選常委,n個中央委員選出l名政治局委員,再從其中選出r名常委 選常委,再選非常委政治局委員 兩種選法都無遺漏,無重復(fù)地給出可能的方案，應(yīng)該相等。,n l n n-r l r r l-r,若干等式及其組合意義,5. ( )+( )+( )=2 , m0, (5) 證1(x+y) =()x y ,令x=y=1,得(5) 組合證 1,m的所有方案.每一子集都可取1,m或不取.這樣有2 個方案.另可有0-子集(空集),1-子集,m-子集.,m m m m 0 1 m,m k m-k,m m k k=0,m,若干等式及其組合意義,6. ( )-( )+( )-( )=0 (6) 證1 在(x+y) =( )x y 中令x=1,y=-1即得.,n n n n 0 1 2 n,n n-k k,n k,n k=0,應(yīng)用舉例,例某保密裝置須同時