組合數(shù)學(xué)(第4章4.3).ppt

第四章：生成排列和組合,4.4 生成r-組合 4.5 序關(guān)系 北京航空航天大學(xué),主要內(nèi)容,生成r-組合算法 偏序和等價關(guān)系,4.4 生成r-組合,集合1,2,3,4的2-組合： 1，2； 1，3; 2，3; 1，4; 2，4; 3，4 字典序：令S=1,2,n, 設(shè)A，B是S的兩個r-組合，若ABAB中的最小整數(shù)屬于A，則稱A先于B。,S的r-組合可寫成如下形式： a1,a2,ar 其中， 1a1a2,ar n 可按字典排序方式排列。,例,S=1,2,3,4,5,6,7,8,9的5-組合按字典序的第一個是：12345, 最后一個：56789 12389的后繼是12456,定理4.41,令a1a2ar是1,2,n的一個r-組合, 在字典序中, 第一個r-組合是12r, 最后一個r-組合是(n-r+1) (n-r+2)n, 設(shè)a1a2ar (n-r+1) (n-r+2)n。令k是滿足akn且使得ak+1不同于a1a2ar中任一數(shù)的最大整數(shù)。那么, 在字典序中, a1a2ar的直接后繼是a1a2ak-1 (ak+1)(ak+r-k+1).,證明：第一個1,2,r; 最后一個(nr+1) (nr+2)n由定義可知。 設(shè)a1a2ar不是最后一個r-組合，確定k使得akn且ak+1不同于a1a2ar中任一數(shù)的最大整數(shù)。有兩種情況： （1）k=r時, ar=akn; （2）kr時, ak+2=ak+1+1, ak+3=ak+2+1, , ar=n。,那么， a1a2ar a1ak1ak (nr+k+1) (nr+k+2 )n. 其中，ak+1 ak+1=nr+k+1。 因此，a1a2ar是以a1ak1ak開始的最后的r-組合。而a1ak-1(ak+1)(ak+2)(ak+r-k+1)是以a1ak1(ak+1)開始的第一個r-組合，結(jié)論成立。,字典序r-組合生成算法,初始： a1a2ar12r 當(dāng)a1a2ar (nr+1) (nr+2)n時，Do 1）確定最大整數(shù)k, 使得ak+1 n，且ak+1ai (i=1,2,r) 2) 用a1a2ak-1 (ak+1)(ak+rk+1)替換a1a2ar.,例,應(yīng)用算法生成1,2,6的4-組合. 12341235123612451246 12561345134613561456 23452346235624563456,定理4.4.2,1,2,n的r-組合a1a2ar出現(xiàn)在1,2,n的r-組合中的字典序中的位置號如下：,證明：計算在a1a2ar之后r-組合個數(shù)。 1) 在a1a2ar后面存在 個組合，使得其第一個元素大于a1. 2）在a1a2ar后面存在 個組合，其第一個元素是a1，第二個元素大于a2。 r)在a1a2ar后面存在 個組合，從a1a2ar-1開始，第r個元素大于ar。 而總數(shù)為 ，結(jié)論成立。,例. 求1,2,8的4-組合中1258的字典序位置。 解：1258的位置是：,4.5 偏序和等價關(guān)系,定義（關(guān)系）：設(shè)X是一個集合，X上的關(guān)系定義為XX上的子集，令關(guān)系R X X，若（a, b）R ,則稱a和b有關(guān)系R，記為aRb; 否則稱a和b沒有關(guān)系R.,定義2,設(shè)R是X上的關(guān)系，那么R可能具有下列性質(zhì): 自反性: 若對 xX, 均有xRx; 反自反性: 若對 xX, 均有x x; 對稱性: 對 x,yX, 若xRy, 則必有yRx; 反對稱性: 對 x,yX, xy, 若xRy; 則必有y x; 傳遞性: 對 x,y,zX, 若xRy, yRz, 則必有xRz;,定義3,設(shè)R是X上的二元關(guān)系 偏序關(guān)系: 若R滿足自反性, 反對稱性和傳遞性, 則稱R是X上的偏序關(guān)系. 記為” ”. 在其上定義了偏序關(guān)系的集合稱偏序集, 記為(X, ). 嚴(yán)格偏序關(guān)系: 若R滿足反自反性, 反對稱性和傳遞性, 則稱R是X上的嚴(yán)格偏序關(guān)系. 記為”. 全序關(guān)系: 對x,yX, 若xRy或yRx, 則稱x和y是可比的, 否則稱x和y是不可比的; 若偏序關(guān)系R使X中任兩個元素都是可比的, 則R是X上的全序關(guān)系, 記為”, 此時(X, )稱全序集. 等價關(guān)系: 若R滿足自反性, 對稱性和傳遞性, 則稱R是X上的等價關(guān)系. 記為”或”=”.,定義4: 偏序集(P, )中, 設(shè)a,bP 覆蓋: 若ab, 則稱b是a的覆蓋; 直接覆蓋: 若ab, 且不存在xP, 使得ax, xb, 則稱b是a的直接覆蓋.,偏序集的幾何表示,當(dāng)b是a的直接覆蓋時,b與a畫一條線段, b在a的上方. 例. X=1, 2, 3, 畫出偏序集(P(A), )的幾何表示圖。,全序集: x1 x2 x3 x4,例 :X=1, 2, 3, 4, 5, 6, 7, 8, ” ”定義為整除關(guān)系, 畫出偏序集(P, )的圖.,1,2,3,5,7,4,6,8,定義4: 偏序集(P, )中, 若 mP, 對 xP, 均有x m, 則稱m是P的最大元.若nP, 對xP, 若n x, 則必有n=x, 稱n是P的極大元. 性質(zhì): (1)偏序集未必存在最大元(最小元), 若存在必唯一；(2)有限偏序集一定存在極大元(極小元), 但未必唯一.,定理4.5.1 設(shè)X是n個元素的有限集, 那么, 在X的全序和排列之間存在一一對應(yīng). 特別地, X上的不同全序個數(shù)是n! . 證明：設(shè)是X上的一個全序, 對應(yīng)到X的一個排列：a1, a2,an, 其中a1 a2an 對n歸納證明，n1時成立。 * 當(dāng)n1，證明X對于存在極小元a1。,對集合Xa1應(yīng)用歸納假設(shè)，得到與對應(yīng)的一個排列a2,a3,an，滿足 a2a3an， 那么，a1,a2,a3,an是X的一個排列。 反之，任何一個排列也對應(yīng)一個全序。 證完。,定義5: 令1和2是集合X上的兩個偏序, 對于a,bX,若有a1b, 則必有a2b, 那么稱偏序集(X, 2)是偏序集(X, 1)的擴(kuò)張. 一個偏序可以擴(kuò)張為一個全序。,定理4.5.2 令(X, )是一個有限偏序集, 則存在X上的線性序, 使得(X, )是(X, )的一個擴(kuò)展. 證明：偏序的線性擴(kuò)展算法，對集合 X=x1,x2,xn的排序問題，滿足：若xi xj, 則排序xi先于 xj 。,算法描述,1）選出X的一個極小元x1. 2）求出集合Xx1的極小元x2。 n) 剩下元素xn. 可證明x1,x2,xn是(X, )的線性擴(kuò)展。,證明：,需要證明對ij有 xixj。 反證法。假設(shè)存在xjxi， ij，注意到算法中xi先于xj選出，因此，由算法xi是包含了xj的集合的極小元，與xjxi矛盾。,例4：X=1,2,3,4,5,6,7,8, “”定義為整除關(guān)系, 確定(X, )的一個線性擴(kuò)展.,1,2,3,5,7,4,6,8,等價關(guān)系與劃分,定義6: 對于X中每一個元素a, a的等價類定義為所有與a等價的元素構(gòu)成的集合.記為a=x xX , xa . 例：整數(shù)集Z中，模m同余是等價關(guān)系。那么，有m個等價類：0,1,m-1. 其中，0=km| kZ 1=lm+1| lZ,定理4.5.3 X的全部等價類構(gòu)成X的一個劃分, 反之, X的任一個非空劃分對應(yīng)X的一個等價類. 證明：(1) 由一個等價關(guān)系構(gòu)造X的一個劃分。每個等價類非空，且對xX, xx,