網(wǎng)上找一些數(shù)學組合all

1、組合數(shù)學講稿 ( 主講: 黃艷新 ) 第33頁 共33頁第三章 排列與組合3.1 兩個基本的計數(shù)原理例3：有6個桔子和9個蘋果，要求藍子中至少有一個水果，問可以裝配成多少種不同的水果藍？區(qū)分兩種不同的計數(shù)類型：（1）對元素的有序擺放數(shù)或選擇數(shù)的計數(shù)。a)沒有重復的元素b)有重復的元素（無限重復或有限重復）（2）對元素的無序擺放數(shù)或選擇數(shù)的計數(shù)。a)沒有重復的元素b)有重復的元素（無限重復或有限重復）定義：與順序有關的擺放或選擇稱 排列。與順序無關的擺放或選擇稱 組合。3.2 集合的排列（一）線性排列定義： 從n個元素中取出r個元素的有序擺放，稱n元素集合的r-排列。 用P（n, r）表示n元素

2、集合的全部r-排列數(shù)。定理3.2.1：對于整數(shù)n和r, r n, 有： P（n, r）= n (n-1) (n-2) 、(n-r+1)=n! /(n-r)!其中：定義n!= n (n-1) (n-2)、2 1約定：（1）0！=1 （2）當rn時，P（n, r）=0例1：將數(shù)字1，2，、，15 放入一個44的方陣中，問共有多少種擺放方法？若放入66的方陣中，共有多少種擺放方法？例2：有多少個取自1，2，、，9的各位互異的7位數(shù)，使得5和6不以任何順序相繼出現(xiàn)？（二）循環(huán)排列定義：把元素排成首尾相連的一個圈，只考慮元素間的相對順序的排列稱循環(huán)排列。定理3.2.2n個元素集合的循環(huán)r排列個數(shù)為：P（

3、n, r）/r = n! /r(n-r)!特別地，n元素的循環(huán)排列個數(shù)=(n-1)!例3：10個人圍坐一個圓桌，其中2個人不愿彼此挨著就座，問有多少種座位擺放方法？3.3 集合的組合定義：從n個元素中無序地取出r個元素，稱n元素集合的r-組合。 用表示n元素集合的全部r-組合數(shù)。定理3.3.1：對于整數(shù)n和r, r n, 有： P（n, r）=r! 即 = P（n, r）/r! =n!/r!(n-r)!約定：（1）=1 （2）當rn時， =0推論3.3.1：對于整數(shù)r，0r n， =例1：平面上25個點，假設不存在3點共線情況，問這些點可以組成多少條直線？多少個三角形？例2：如果每個詞都包含3

4、，4或5個元音，那么字母表中26個字母可以構(gòu)造多少個8字母詞？（假設每個詞中的字母使用次數(shù)沒有限制）定理3.3.2：下述公式成立：+=2n .例3：用不同計數(shù)法證明： =n(n-1)/234 多重集的排列定理3.4.1：令S是多重集，它有k個不同的元素，每個元素都有無限重復次數(shù)，那么，S的r-排列個數(shù)為kr .例1：具有4位數(shù)字的三進制數(shù)的個數(shù)是多少？定理3.4.2：令S是多重集，它有k個不同的元素，每個元素的重復數(shù)分別為n1，n2，、，nk，那么，S的排列數(shù)=，其中n= n1+n2+、+nk例2：求字母多重集1.m, 4.I, 4S, 2.P 的排列數(shù)例3：在88的棋盤上，對于8個非攻擊型車

5、有多少種可能的擺放法？定理3.4.3：有n個車共k種顏色，其中第一種顏色的車有n1個，第二種顏色的車有n2個， 、 ，第k種顏色的車有nk個，那么，把這些車放到nn的棋盤上，使得沒有車能相互攻擊的擺放方法數(shù)為：. n! *懸而未決的問題：多重集S=n1.a1, n2.a2, 、, nk.ak ，令n= n1+n2+、+nk ，求S的r排列數(shù)？其中rm的整數(shù)p的方向.算例: (n=4)4.2 排列中的逆序定義：令i1 i2 in 是集合1,2,n的一個排列，如果 0 k iL , 稱數(shù)對（ik ，iL）是排列的一個逆序。例：31524的逆序定義：令aj表示排列i1 i2 in中數(shù)j的逆序數(shù)，稱a

6、1, a2, an為排列i1 i2 in 的逆序列。例：排列31524的逆序列逆序列的性質(zhì)：(1) 0a1 n-1, 0a2 n-2, , 0an-1 1, an =0。 (2) 逆序列數(shù)有n!個。定理4.2.1:令b1, b2, bn為滿足 0b1 n-1, 0b2 n-2, , 0bn-1 1, bn =0的整數(shù)序列，那么存在集合1,2,n的唯一一個排列，使它的逆序列為b1, b2, bn 。證明：（構(gòu)造性證明）算法一：n:寫出整數(shù)nn-1:考慮bn-1，若 bn-1 =0，則n-1必在n的前面。 若bn-1 =1：則n-1必在n的后面。n-2:考慮bn-2，若 bn-2 =0，則n-2必

7、在上一步得到的排列的前面。 若 bn-2 =1，則n-2必在上一步得到的排列的兩個數(shù)中間。 若 bn-2 =2，則n-2必在上一步得到的排列的后面。1: 考慮b1，把1放在上一步得到的排列的第b1 個數(shù)的后面。由算法可知，從n, n-1,2,1每一步都根據(jù)b1, b2, bn 唯一地確定1,2,n在排列中的位置，兩者存在一一對應關系。算法二：設有n個位置，標志為1,2,n1:把1放在b1+1位置上；2:把2放在第b2+1個 空 位置上；k: 把k放在第bk+1個 空 位置上；n: 把k放在余下的 空 位置上；由算法可知，根據(jù)b1, b2, bn 唯一地確定1,2,n在排列中的位置，兩者存在一一

8、對應關系。例1：已知1,2,8的一個排列的逆序列為：5，3，4，0，2，1，1，0，確定此排列。4.3 生成組合令集合S=xn-1, xn-2, x-1, x0 ，生成S的所有2n個組合。算法：從n元組an-1an-2a1a0=000開始, 當an-1an-2a1a0=111時算法結(jié)束, 做:(1)求出使得aj=0的最小整數(shù)j; (2)用1代替aj , 并且用0代替aj-1, aj-2 , , a0 . 算法正確性證明:幾種不同的組合輸出序:字典序組合壓縮序格雷(Gray)碼序n階反射格雷(Gray)碼的遞歸定義:1階反射格雷(Gray)碼是 ;設n1, 且n-1階反射格雷(Gray)碼已經(jīng)構(gòu)

9、造好,首先順序列出n-1階反射格雷(Gray)碼的全部n-1元組, 并把0加到全部n-1元組的開頭; 然后再反序列出n-1階反射格雷(Gray)碼的全部n-1元組, 并把1加到全部n-1元組的開頭.定義:設an-1an-2a1a0是01的n元組, 定義函數(shù)為:( an-1an-2a1a0)= an-1+an-2+a0算法: (以反射格雷(Gray)碼序生成全部 01的n元組)從n元組an-1an-2a1a0=000開始, 當an-1an-2a1a0=100時算法結(jié)束, 做:(1)計算( an-1an-2a1a0)= an-1+an-2+a0(2)若( an-1an-2a1a0)是偶數(shù), 則改變

10、a0(01 或 10)(3) 若( an-1an-2a1a0)是奇數(shù), 確定這樣的j, 使得對所有ij, 有ai=0. 改變aj+1(01 或 10).例1：生成4階反射格雷(Gray)碼.定理4.3.1(算法正確性證明)上述算法產(chǎn)生n階反射格雷(Gray)碼.例2：在8階反射反射格雷(Gray)碼中,求10100110的后繼,00011101的前驅(qū).4.4 生成r組合定理4.41:令a1a2ar是1,2,n的一個r-組合, 在字典序中, 第一個r-組合是12r, 最后一個r-組合是(n-r+1) (n-r+2)n, 設a1a2ar(n-r+1) (n-r+2)n, 令k是滿足akn且使得ak

11、+1不同于a1, a2,ar 中任一數(shù)的最大整數(shù), 那么, 在字典序中, a1a2ar的直接后繼是a1a2ak-1 (ak+1)(ak+r-k+1).例1：應用算法生成1,2,6的4-組合.定理4.4.21,2,n的r-組合a1a2ar出現(xiàn)在1,2,n的r-組合中的字典序中的位置號如下:-例2：求1,2,8的4-組合中1258的字典序位置.4.5 偏序和等價關系定義1：設X是一個集合，X上的關系定義為X X上的子集（其中X X是集合X的序偶的集合，即X X=（a,b） a,bX ），令關系R X X，若（a,b）R ,則稱a和b有關系R，記為aRb;否則稱a和b沒有關系R ,記為 ab.定義2

12、：設R是X上的關系，R=(x,y)| x, yX 且xRy , 那么R可能具有下列性質(zhì):自反性: 若對 xX, 均有xRx;反自反性: 若對 xX, 均有xx;對稱性: 對 x,yX, 若xRy, 則必有yRx;反對稱性: 對 x,yX, xy, 若xRy; 則必有yx;傳遞性: 對 x,y,zX, 若xRy, yRz, 則必有xRz;定義3: 設R是X上的二元關系偏序關系:若R滿足自反性, 反對稱性和傳遞性, 則稱R是X上的偏序關系. 記為” ”. 在其上定義了偏序關系的集合稱偏序集, 記為(X, ).嚴格偏序關系:若R滿足反自反性, 反對稱性和傳遞性, 則稱R是X上的嚴格偏序關系. 記為”

13、.全序關系:對x,yX, 若xRy或yRx, 則稱x和y是可比的, 否則稱x和y是不可比的; 若偏序關系R使X中任兩個元素都是可比的, 則R是X上的全序關系, 記為”, 此時(X, )稱全序集.等價關系:若R滿足自反性, 對稱性和傳遞性, 則稱R是X上的等價關系. 記為”或”=”.定義4: 偏序集(P, )中, 設a,bP覆蓋:若ab, 則稱b是a的覆蓋;直接覆蓋:若ab, 且不存在xP, 使得ax, xb, 則稱b是a的直接覆蓋.偏序集的幾何(哈斯圖)表示:方法:當b是a的直接覆蓋時,b與a畫一條線段, b在a的上方.例1:X=1, 2, 3, 畫出偏序集(P(A), )的哈斯圖.例2:X=

14、1, 2, 3, 4, 5, 6, 7, 8, ” ”定義為整除關系, 畫出偏序集(P, )的哈斯圖.例3:P=1, 2, 3, 4, 5, ” ”定義為實數(shù)域小于等于關系,畫出全序集(P, )的哈斯圖.定義4:偏序集(P, )中, 若 mP, 對 xP, 均有x m, 則稱m是P的最大元.若nP, 對xP, 若n x, 則必有n=x, 稱n是P的極大元.同理定義 最小元和極小元.性質(zhì):(1)偏序集未必存在最大元(最小元), 若存在必唯一.(2)偏序集一定存在極大元(極小元), 但未必唯一.定理4.5.1設X是n個元素的有限集, 那么, 在X的全序和排列之間存在一一對應. 特別地, X上的不同

15、全序個數(shù)是n! .定義5:令1和2是集合X上的兩個偏序, 對于a,bX,若有a1b, 則必有a2b, 那么稱偏序集(X, 2)是偏序集(X, 1)的擴展.定理4.5.2令(X, ) 是一個有限偏序集, 則存在X上的線性序(全序) , 使得(X, )是(X, )的一個擴展.例4：X=1,2,3,4,5,6,7,8, “”定義為整除關系, 確定(X, )的一個線性擴展.定義6:對于X中每一個元素a, a的等價類定義為所有與a等價的元素構(gòu)成的集合.記為a=x xX ,xa .定理4.5.3X的全部等價類構(gòu)成X的一個劃分, 反之, X的任一個非空劃分對應X的一個等價類.第五章 二項式定理5.1 二項式

16、定理定理5.1令n是一個正整數(shù), 那么對于變量x,y(可以是任意實數(shù))有:(x+y)n= xn + xn -1y + xn -2y2+ yn-1+ yn.即(x+y)n= xn -kyk二項式定理的幾個其它形式:(1)(x+y)n= xn -kyk(2)(x+y)n= xkyn-k(3)(x+y)n= xkyn-k (4)(1+x)n= xk5.2 Pascal 公式定理5.2對于滿足1kn-1的所有整數(shù)k和n, 有=+5.3 一些有用的恒等式 k=n +=2n -+(-1)k +(-1)n=0 1+2+n=n2n-1 n(n+1) 2n-2=k2(n 1) 2=定義1:令r可取任意實數(shù), k

17、可取任意整數(shù), 定義的擴展為:=易證擴展定義仍使Pascal公式成立:=+ += +=5.4 二項式系數(shù)的單峰性定義1:設序列s0, s1, s2, sn ,若存在一個整數(shù)t, 0tn, 使得:s0 s1 s2 st , st st+1 st+2 sn那么,稱序列是單峰的.定理5.4.1令n為正整數(shù), 二項式系數(shù)序列是單峰序列, 精確地說,若n是偶數(shù):.若n是奇數(shù):.定義2:設x為任意實數(shù), 令x 表示大于或等于x的最小整數(shù), 稱強取整(上取整);x 表示小于或等于x的最大整數(shù), 稱弱取整(下取整).推論5.4.2二項式系數(shù), 的最大者為:=定義3:(1) 集合的鏈:令S是n個元素的集合, C

18、是S的組合的集合,若C中任兩個元素都存在包含關系, 稱C是S的一個鏈.(2) 對稱的鏈:C是S的一個鏈, 若( = 1 * roman i)C中依嚴格偏序關系排成的序列, 每一項都比前一項多一個元素;( = 2 * roman ii)序列第一個組合的大小加上最后一個組合的大小是n.則稱C是對稱的鏈.(3) 集合的反鏈(雜置Clutter)若C中任一個組合都不包含于其它組合中, 稱C是反鏈.定理5.4.3(Sperner定理):令S為n個元素的集合, 則S的反鏈(雜置)最多包含個組合.5.5 多項式定理定理5.5:令n為一正整數(shù), 對所有的x1, x2, xt, (x1 +x2+ xt)n=x1

19、n1 x2n2 xtnt 其中, 求和是對n1+ n2+ nt=n的所有非負整數(shù)解進行.例1：求(2x1-3x2+5x3)6被展開時,x13 x2 x32 的系數(shù).5.6 牛頓二項式定理定理5.6.1:令 是一個實數(shù), 那么對于所有滿足 0 x y 的變量x , y有:(x+y)= xky - k其中：=有用的級數(shù)展開式： z 1, (1 + z)= zk取 為負整數(shù) -n, 則=(-1)k z 1, (1 + z) -n= zk= (-1)k zk z 1, (1 - z) -n= (-1)k zk= zk特別地, (1 + z) 1= (-1)k zk ; (1 - z) 1=zk=5.7

20、 再論偏序集定義1:令(X, )是一個有限偏序集, 反鏈是X的一個子集, 其中任意兩個元素都不可比; 鏈是X的一個子集, 其中任意兩個元素都是可比的.定理5.7.1:令(X, )是一個有限偏序集, 并令r 是鏈的最大的大小, 則X可以被劃分成r 個但不能再少的反鏈.定理5.7.2:令(X, )是一個有限偏序集, 并令m 是反鏈的最大的大小, 則X可以被劃分成m 個但不能再少的鏈.第六章 容斥原理定理6.1.1集合S的不具有性質(zhì)P1, P2, Pm的物體的個數(shù)由下式給出: =S-+-+(-1)m其中:第一個求和對集合1,2,m的所有的1-組合進行, 第二個求和對集合1,2,m的所有的2-組合進行

21、,依此類推.推論6.1.2集合S的具有性質(zhì)P1, P2, Pm之一的物體的個數(shù)由下式給出:=-+(-1)m+1例1:求1到1000不能被5, 6和8整除的數(shù)的個數(shù).6.2 多重集的組合(第三章) 懸而未決的問題：令多重集S=n1.a1, n2.a2, 、, nk.ak ，n= n1+n2+、+nk ，求S的r-組合數(shù)，其中0rn.上述問題相當于求解方程x1 +x2+ 、+ xk =r 的滿足條件0 x1 n1 , 0 x2 n2 ,、, 0 xk nk 的整數(shù)解的個數(shù)。例1:確定多重集T=3.a, 4.b, 5.c的10-組合的個數(shù). 例2:求滿足 1x15, -2x24, 0 x35, 3x

22、49條件的方程x1+ x2+ x3+ x4=18的整數(shù)解個數(shù).6.3 錯位排列定義1:設X=1,2,n, 它的排列用i1 i2in 表示, 錯位排列就是問有多少種排列方法使得i1 1, i2 2, , in n.我們用Dn表示錯位排列個數(shù). 顯然, D1 =0, D2 =1.定理6.3.1對于n1,Dn =n!(1-+-+(-1)n)一個有趣的結(jié)論：e-1=1-+-+ (e=2.718)即 e-1=+(-1)n+1+(-1)n+2當n大于7時, e-1和的誤差小于(約1/1000), 因此10位紳士隨機拿一頂帽子, 每人都錯拿的概率是e-1(37%). 100000位紳士隨機拿一頂帽子, 每人

23、都錯拿的概率是仍e-1(37%).推論6.3.2Dn 滿足如下遞推關系:Dn =(n-1)( Dn-2 - Dn-1 ) (n=3,4,)Dn =nDn-1 + (-1)n (n=2,3,)6.4 帶有禁止位置的排列定義1:令X1, X2, Xn 是1,2,.,n的子集(可以是空集, 子集間可能有重疊) , 用P(X1, X2, Xn)表示1,2,n的所有排列i1 i2in 的集合, 要求:i1 不在X1內(nèi), i2 不在X2內(nèi), in 不在Xn內(nèi). 稱這種排列為帶有禁止位置的排列，用 P(X1, X2, Xn)表示滿足上述條件的排列數(shù).例：在nn的棋盤上放置n個非攻擊型車，現(xiàn)在規(guī)定一些禁止位置

24、：P1：表示在第一行的車要放在X1的列上（X1是1，2，、，n的子集）；P2：表示在第一行的車要放在X2的列上（X2是1，2，、，n的子集）；、Pn：表示在第一行的車要放在Xn的列上（Xn是1，2，、，n的子集）；滿足性質(zhì)Pj的n個非攻擊型車的擺放方法相當于第j行的車只能放在Xj規(guī)定的列上，即相當于1，2，、，n的n-排列i1 i2 in ,滿足ij Xj . 設滿足性質(zhì)Pj 的n-排列的集合為Aj ，（j=1,2,n）. 問題就是求 。定理6.4.1將n個非攻擊型車放到有禁止位置的n行n列棋盤上的方法數(shù)等于:n!-r1(n-1)!+ r2(n-2)!+(-1)k rk(n-k)!+(-1)n

25、 rn.例1:6個非攻擊型車放到66棋盤上, 禁止位置如圖所示, 求放置方法數(shù).6.5 其它的禁排位置問題定義1:設集合S=1,2,n, 它的不出現(xiàn)12, 23, ,(n-1)n的排列稱相對禁止位置排列. 相對禁止位置排列的排列數(shù)用Qn 表示.定理6.5.1對于n1,Qn =n! -(n-1)! + (n-2)! +(-1)n 1!Qn 和Dn 的關系:Qn = Dn + Dn-1 (n2)第七章 遞推關系和生成函數(shù)7.1 某些數(shù)列（1）等差數(shù)列（算術數(shù)列）h0, h0+q, h0+2q, , h0+nq,遞推關系：hn= hn-1+q一般項： hn= h0+nq前n+1項和：sn= (n+1

26、)h0+q(n)(n+1)/2（2）等比數(shù)列（幾何數(shù)列）h0, qh0, q2h0, , qnh0,遞推關系：hn= qhn-1一般項： hn= qnh0前n+1項和：sn= h0(1-qn+1)/(1-q) 例1：確定平面一般位置上的n個互相交疊的圓所形成的區(qū)域數(shù)。（互相交疊是指每兩個圓相交在不同的兩個點上；一般位置是指沒有同心圓）例2：年初把性別相反的一對新生兔子放進圍欄，從第二個月開始每月生出一對性別相反的兔子，每對新兔也從第二個月開始每月生出一對性別相反的兔子，問一年后圍欄內(nèi)共有多少對兔子。定義1：設f0=0, f1=1, 那么滿足遞推關系fn= fn-1+ fn-2, 的序列叫斐波那

27、契（Fibonacci）序列。結(jié)論：Fibonacci序列的部分和為sn= f0+ f1+ fn= fn+2-1.定理7.1.1：Fibonacci序列的一般項公式為：fn=（）n -（）n定理7.1.2沿Pascal三角形左邊向上對角線上的二項式系數(shù)和是Fibonacci數(shù),即fn=+, 其中:k=.7.2 線性齊次遞推關系定義1:令h0, h1, h2, hn,是一個數(shù)列,若存在量a1, a2, ,ak和bn(ak0,每個量是常數(shù)或依賴于n的數(shù))使得:hn= a1hn-1+ a2hn-2+ akhn-k+bn (nk)則稱序列滿足k階線性遞推關系. 若bn=0,稱齊次的;若a1, a2,

28、,ak取常數(shù),稱常系數(shù)的.定理7.2.1令q為一個非零數(shù),則hn=qn是常系數(shù)線性齊次遞推關系hn= a1hn-1+ a2hn-2+ akhn-k (ak0,nk) (1)的解,當且僅當q是多項式方程xk-a1xk-1- a2xk-2- ak=0(2)的一個根.若多項式方程有k個不同的根q1, q2, qk,則hn=c1q1n+ c2q2n+ ckqkn(3)是下述意義下(1)的一般解: 無論給定h0, h1, ,hk-1什么初始值,都存在c1, c2, ck使得(3)式是滿足(1)式和初始條件的唯一的序列.例1:求滿足初始值h0=1, h1=2和h2=0的遞推關系:hn= 2hn-1+ hn

29、-2- 2hn-3定理7.2.2令q1, q2, qt為常系數(shù)線性齊次遞推關系:hn= a1hn-1+ a2hn-2+ akhn-k (nk)的特征方程的互異的根,此時,如果qi是si的重根,則該遞推關系對qi的部分一般解為:Hn(i) = c1qin+ c2nqin+ csinsi-1qin遞推關系的一般解為:hn= Hn(1) + Hn(2) + Hn(t) 例2:求解遞推關系hn= -hn-1+ 3hn-2+ 5hn-3+ 2hn-4 (n4)滿足初始條件h0=1, h1=0, h2=1和h3=2的解.7.3 非齊次遞推關系一般方法總結(jié):求齊次關系的一般解求非齊次關系的一個特解將一般解和

30、特解結(jié)合,通過初始條件確定一般解中出現(xiàn)的常系數(shù)值.根據(jù)非齊次項bn 來嘗試某些類型的特解:若bn =d(常數(shù)), 嘗試hn =r(常數(shù));若bn =dn+c(d,c是常數(shù)), 嘗試hn =rn+s(r,s是常數(shù));若bn =fn2+dn+c(f,d,c是常數(shù)), 嘗試hn =rn+sn+t(r,s,t是常數(shù));若bn =dn(d是常數(shù)), 嘗試hn =pdn(p是常數(shù));例1:解hn= 3hn-1- 4n (n1), 初始值h0=2.例2:解hn= 3hn-1+ 3n (n1), 初始值h0=2.7.4 生成函數(shù)定義1:令序列h0, h1, hn為一無窮序列,其生成函數(shù)定義為:g(x)= h0

31、+ h1x+ h2x2+ hnxn+例1:設m是正整數(shù),求序列,的生成函數(shù).例2:設是實數(shù),求序列,的生成函數(shù).例3:設k是正整數(shù),求序列h0, h1, hn的生成函數(shù),其中一般項hn等于方程e1 + e1+ +ek =n的非負整數(shù)解個數(shù).解: hn相當于具有無限重復次數(shù)的k 個不同元素的n組合個數(shù), hn=,其生成函數(shù)g(x)=xn=反向思考該問題:若已知生成函數(shù)g(x)=,那么=.=(1+x+x2+) (1+x+x2+) (1+x+x2+)=. 其展開項xn= xe1. xe2. .xek = xe1+e2+.ek, 它的系數(shù)hn相當于方程e1 + e1+ +ek =n的非負整數(shù)解個數(shù),

32、hn=, 相當于根據(jù)生成函數(shù)求解出具有無限重復次數(shù)的k 個不同元素的n組合個數(shù)hn. 若e1 , e1,ek 有不同的約束, 表現(xiàn)為不同的生成函數(shù), 若我們能求出該生成函數(shù)對應的序列一般項hn.那么就相當于在某種約束下求解出k 個不同元素的n組合個數(shù)hn.例4:確定蘋果,香蕉,橘子和梨的n組合個數(shù),其中每個n組合中,蘋果的個數(shù)是偶數(shù),香蕉的個數(shù)是奇數(shù),橘子的個數(shù)在04之間,而且至少有一個梨.例5:確定蘋果,香蕉,橘子和梨的袋裝水果的袋數(shù)hn(即n組合數(shù)),其中每袋中蘋果的個數(shù)是偶數(shù),香蕉的個數(shù)是5的倍數(shù),橘子的個數(shù)最多4個,梨子的個數(shù)是0或1.7.5 遞歸和生成函數(shù)利用生成函數(shù)求解n階常系數(shù)線

33、性齊次遞推關系:例1:求解初始值h0=1和h1=-2的遞推關系hn= 5hn-1-6hn-2 (n2)定理7.5.1令h0, h1, h2, hn,為滿足k階常系數(shù)線性齊次遞推關系:hn= c1hn-1+ c2hn-2+ ckhn-k (ck0,nk)(1)的數(shù)列,則它的生成函數(shù)g(x)形如:g(x)=(2)其中:q(x)是具有非零常數(shù)次的k 次多項式,p(x)是小于k 次的多項式.反之, 給定這樣的多項式p(x)和q(x), 則存在序列h0, h1, h2, hn,滿足(1)式的k階常系數(shù)線性齊次遞推關系, 其生成函數(shù)由(2)式給出.關于解方程的已知結(jié)論:(1)對于4次以及4次以下的方程,目

34、前已有代數(shù)解法.(在復數(shù)域內(nèi)求解)(2)阿貝爾定理:5次以及更高次的代數(shù)方程沒有一般的代數(shù)解法.7.6 一個幾何的例子定義1:設有平面或空間中的點集k, 若k中任意兩點p和q的連線pq上的所有點都在k內(nèi),稱k是凸的.定理7.6.1通過畫出在區(qū)域內(nèi)不相交的對角線,令hn表示具有n+1條邊的凸多邊形區(qū)域分成三角形區(qū)域的方法數(shù),定義h1=1,則hn滿足如下遞推關系:hn=h1hn-1+ h2hn-2+ h1hn-1+ hn-1h1= (n2)該遞推關系的解為:hn=7.7 指數(shù)生成函數(shù)定義1:設序列h0, h1, h2, hn, 定義其指數(shù)生成函數(shù)為:g(e)(x)= h0+ h1+ h2+ hn定

35、理7.7.1令S=n1.a1, n2.a2, nk.ak 為一多重集,其中: n1, n2, nk 均為非負整數(shù),令hn表示S的n排列數(shù),則序列h0, h1, h2, hn,的指數(shù)生成函數(shù)g(e)(x)由:g(e)(x)=fn1(x). fn2(x) fnk(x)(1)給定,其中,對于I=1,2,k, fni(x)= 1+ + + .例1:如果把棋盤上偶數(shù)個方格涂成紅色,試確定用紅色,白色和藍色對1行n列棋盤上的方格涂色方法數(shù).第九章 二分圖中的匹配三個典型問題：在一個有禁止位置的mn棋盤上，能放置非攻擊型車的最多個數(shù)是多少？在一個有禁止位置的mn棋盤上，能放置多米諾牌覆蓋的最多個數(shù)是多少？一

36、個公司有n個工作空缺，需要有一定技能的人填補，同時有m個人申請這些項工作，每人能勝任n項工作中的若干項，問最多有多少項工作能找到合適的人選？9.1 一般的問題描述定義1：令X=x1, x2, ,xm, Y=y1,y2, ,yn,且XY，而是序偶e=(x,y)的集合，其中xX,yY,那么三元組G（X，Y）稱作二分圖。定義2：令G（X，Y）是一個二分圖，邊集的子集M，若M中沒有兩條邊存在公共點，稱M是二分圖G的一個匹配。定義3：設G是一個二分圖，定義（G）M:M是G的一個匹配為二分圖G的最大匹配邊數(shù)。9.2 匹配定義1：G（X，Y），X=x1, x2, ,xm, Y=y1,y2, ,yn，滿足M*

37、=（G）的匹配M*稱為二分圖G的最大匹配。一般M*不唯一，且M*=（G）minm,n。尋找M*的困難點：若已知（G），那么遍歷所有可能的匹配會找到M*，但搜索量巨大；一般（G）并不事先知道，要找到M*，并求出（G）M*難度更大。定義2：令u和v是二分圖G（X，Y）的任意兩個頂點，連接u和v的互異頂點序列：u=u0, u1, u2, , up-1, up=v使得任意兩個相鄰頂點有一條邊連接，即： u0, u1, u1, u2, up-1, up,那么稱序列為二分圖G的一個鏈。鏈長等于序列的邊數(shù)p，若u=v, 鏈也叫圈。定義3：令M為二分圖G（X，Y）中的一個匹配，令是M的補集，即G的不屬于M的邊

38、集合，M。令u和v是頂點，且u和v一個是左頂點（即屬于X），一個是右頂點（即屬于Y），若連接u和v的鏈滿足下列性質(zhì)：（1）的第一、三、五、邊屬于；（2）的第二、四、六、邊屬于M；（3）u和v都不與M的邊相連。那么稱為關于匹配M的交錯鏈，簡稱M-交錯鏈。M-交錯鏈的性質(zhì)：（1）M-交錯鏈的長是奇數(shù)2k+1, k0;（2）設M表示的屬于M的邊集合，表示的屬于的邊集合，那么有：=M1例：定理9.2.1:令M為二分圖G（X，Y）中的一個匹配，則M是最大匹配當且僅當不存在M-交錯鏈。推論9.2.1:若M不是二分圖G的最大匹配，那么必存在M-交錯鏈。進展：得到了最大匹配的特征，即只需找M-交錯鏈，找不到，

39、則M就是最大匹配。困難：搜索M-交錯鏈類似于窮舉，算法上不可行，即在構(gòu)造最大匹配的時候不知算法何時結(jié)束。怎么辦？當找到一個匹配M時，希望能有一種方法直接直接驗證其是否為最大匹配，若不是，則繼續(xù)找（肯定能找到）；若是，則算法結(jié)束。定義4：令G（X，Y）是一個二分圖，S是G的頂點XY的子集，若G中任一條邊的兩個頂點至少有一個屬于S，即：x,yS,對x,y則稱S是G的一個覆蓋。例：定義5：令c（G）minS:S是G的覆蓋，即c（G）是G的覆蓋的最小頂點個數(shù)，稱c（G）為G的覆蓋數(shù)。顯然，G的任一個覆蓋S滿足Sc(G),把滿足Sc(G)的覆蓋S稱為G的最小覆蓋。*圖的最小頂點覆蓋問題是典型的NP難題。

40、引理9.2.2:如果G是一個二分圖，那么（G）c（G）,即二分圖G的最大匹配邊數(shù)不會超過G的覆蓋數(shù)。例：求二分圖G的最大匹配和最小覆蓋的算法：令G（X，Y）是一個二分圖，其中X=x1, x2, ,xm, Y=y1,y2, ,yn，令M為得到的G的任一匹配。 將X的所有不與M的邊相關聯(lián)的頂點標上（*），并稱所有的頂點為未被掃描的，轉(zhuǎn)（2）；如果在上一步?jīng)]有新的標記（例如（*）,（yj）加到X的頂點上，則停止。否則，轉(zhuǎn)（3）；當存在X的被標記但未被掃描的頂點時，選擇一個被標記但未被掃描的頂點，比如xi, 用(xi)標記Y的所有頂點，這些頂點被不屬于M且尚未標記的邊連到xi。現(xiàn)在頂點xi是被掃描的，

41、若X中不存在被標記但未被掃描的頂點時，轉(zhuǎn)（4）；若在步驟（3）中沒有新的標記加到Y(jié)中頂點上，則停止；否則，轉(zhuǎn)（5）；當存在Y中被標記但未被掃描的頂點時，選擇Y中一個被標記但未被掃描的頂點，比如yj, 用(yj)標記X 的所有頂點，這些頂點被屬于M且尚未標記的邊連到y(tǒng)j?，F(xiàn)在頂點yj是被掃描的，若Y中不存在被標記但未被掃描的頂點時，轉(zhuǎn)（2）；例1：如圖，確定二分圖G的最大匹配和最小覆蓋。算法的收斂性證明：定義6：突破點：存在Y中的被標記的點，該點不與M的邊關聯(lián)；非突破點： 算法終止，但未出現(xiàn)突破點，即Y中每一個被標記的頂點都與M的邊關聯(lián)。結(jié)論：在突破點情況，算法成功找到一個M-交錯鏈，因此，可以

42、構(gòu)造一個比M更大的匹配，再重新應用匹配算法。算法的正確性證明：定理9.2.3:設非突破點在匹配算法中發(fā)生，令Xun由X中所有未被標記的頂點組成，并令Ylab由Y的所有被標記的頂點組成，則下列兩個結(jié)論成立：SXunYlab是二分圖G的最小覆蓋；MS，且M是G的最大匹配。推論9.24(Konig定理)：令G（X，Y）是一個二分圖，則（G）c（G）,即二分圖G的最大匹配邊數(shù)等于G的最小覆蓋的頂點數(shù)。定義7：令G（X，Y）是一個二分圖，X和Y的頂點數(shù)均為n,G中有n條邊的匹配稱為完美匹配。定義8：若二分圖G（X，Y）的每一個頂點都與p 條邊關聯(lián)，則稱G是p階正則的。性質(zhì)：若G是p階正則的，那么X和Y必

43、有相同的頂點數(shù)。定理9.2.5p1階正則的二分圖G（X，Y）總有完美匹配。9.3 互異代表系統(tǒng)定義1：令Y為有限集合，A=(A1, A2, ,An)為Y的n 個子集序列，那么，Y中的元素序列（e1, e2, ,en）,其中en Ai（I=1,2,n）稱為A的代表系統(tǒng) 。若e1, e2, ,en是互異的，稱為互異代表系統(tǒng)（System of Distinct Representatives）。簡稱SDR。引理9.3.1 (SDR存在的必要條件)為使集合序列A=(A1, A2, ,An)有SDR，必須滿足下列條件：（MC：成婚條件）：對每一個k=1,2,n,以及從1,2,n選出的k個互異指標i1,

44、 i2, ,ik, 都有：Ai1 Ai2Aikk.定理9.3.2:集合序列A=(A1, A2, ,An)有SDR，當且僅當成婚條件成立。定理9.3.3:A=(A1, A2, ,An)是集合Y的子集序列，那么A的能夠選出使得有SDR的子集的最大個數(shù)由下式給出：Ai1 Ai2Aik+n-k其中表達式右側(cè)表示對于k=1,2,n的所有選擇，以及相應的取自1,2,n的k個互異指標i1, i2, ,ik的所有選擇得到的最小值。例1：設集合序列A1a,b,c, A2b,c, A3b,c, A4b,c, A5c, A6a,b,c,d,確定集合序列可以選出的有SDR的最大子集個數(shù)。9.4 穩(wěn)定婚姻定義1：設有n位女士和n位男士，每位女士按照其對每位男士作為配偶的偏愛程度給每位男士排名次，不允許并列名次出現(xiàn)，因此，每位女士都會給男士排成1,2,n的順序；類似地，每位男士給女士也會有1,2,n的順序排名。使所有n男士和女士都成婚，稱為完備婚姻。顯然，實現(xiàn)完備婚姻地方法數(shù)有n!種。若一個完備婚姻中存在兩位女士A和B及兩位男士