組合數(shù)學(xué)復(fù)習(xí)總結(jié)

1、 組合數(shù)學(xué) 復(fù)習(xí)總結(jié)內(nèi)容1.課程知識結(jié)構(gòu)2.各章知識點知識結(jié)構(gòu)什么是組合數(shù)學(xué)什么是組合數(shù)學(xué)鴿巢原理鴿巢原理排列與組合排列與組合生成排列和組合生成排列和組合二項式系數(shù)二項式系數(shù)容斥原理及應(yīng)用容斥原理及應(yīng)用遞推關(guān)系和生成函數(shù)遞推關(guān)系和生成函數(shù)計數(shù)技巧計數(shù)技巧構(gòu)造算法構(gòu)造算法排列存在性排列存在性二分圖的匹配二分圖的匹配各章要求和重點各章要求和重點第1章 什么是組合數(shù)學(xué)n組合數(shù)學(xué)的研究內(nèi)容組合數(shù)學(xué)是研究離散結(jié)構(gòu)的存在、計數(shù)、分析和優(yōu)化等問題的學(xué)科。n一些重要例子棋盤覆蓋問題第2章 鴿巢原理及應(yīng)用n鴿巢原理簡單形式及鴿巢原理簡單形式及加強形式加強形式若將q1+q2+qnn+1個物體被放進n個盒子內(nèi)，那么

2、，或者第一個盒子至少含有個q1物體，或者第二個盒子至少含有個q2物體，或者第n個盒子至少含有個qn物體nRamsey定理至少掌握Ramsey定理的簡單形式及應(yīng)用。第2章 鴿巢原理及應(yīng)用(續(xù))n用于證明某種排列的存在性，不用于構(gòu)造排列和計數(shù)。n運用鴿巢原理通常需要將問題轉(zhuǎn)化。第3章 排列與組合n主要內(nèi)容主要內(nèi)容兩個基本計數(shù)原理：加法原理、乘法原理集合排列和組合多重集的排列多重集的排列（重點掌握重點掌握）多重集的組合多重集的組合（重點掌握重點掌握）3.2 集合的排列n難點n循環(huán)排列: 把元素排成首尾相連的一個圈，只考慮元素間的相把元素排成首尾相連的一個圈，只考慮元素間的相對順序的排列。對順序的排列

3、。nn個元素集合的循環(huán)r排列個數(shù)為： 特別地，n元素的循環(huán)排列個數(shù)=(n1)! )!(!),(rnrnrrnP3.4 多重集的排列n無限重元素的排列計數(shù)：令S是多重集，它有k個不同的元素，每個元素都有無限重復(fù)次數(shù)，那么，S的r-排列個數(shù)為kr。n多重集的（全）排列計數(shù)：令S是多重集，它有k個不同的元素，每個元素的重復(fù)數(shù)分別為n1，n2，nk，那么，S的排列數(shù)等于!21knnnn3.5 多重集組合n無限重數(shù)多重集組合：令S是多重集，它有k個不同的元素，每個元素都有無限重復(fù)次數(shù)，那么，S的r-組合個數(shù)為nS的r-組合個數(shù)等于方程x1+x2+xk=r的非負(fù)整數(shù)解的個數(shù)。 r1-kr= 1-k1-kr

4、3.5 多重集組合（續(xù)）n多重集S=n1a1, n2a2, , nkak，n= n1+n2+nk ，求S的r-組合數(shù)，其中0rn。容斥原理方法生成函數(shù)方法第4章：生成排列和組合n主要算法相關(guān)問題n排列生成算法遞歸方法鄰位替換逆序生成算法第4章：生成排列和組合（續(xù)）n生成組合算法字典序組合壓縮序反射Gray序n生成r-組合算法字典序r-組合生成算法第5章 二項式系數(shù)111knknknPASCAL公式：0)(kkkyxkyx牛頓二項式：nnkxnknx01)1 (1第6章 容斥原理及應(yīng)用n主要內(nèi)容容斥原理：集合交、并的計數(shù)容斥原理的應(yīng)用（1）多重集組合計數(shù)（2）特殊問題排列計數(shù)：錯位排列、禁位排列

5、等6.1 容斥原理n集合S不具有性質(zhì)P1,P2,Pm的物體的個數(shù)：|21mAAA|S|Ai|+|Ai Aj| |Ai Aj Ak |+(1)m|A1A2Am|容斥原理在多重集組合計數(shù)應(yīng)用n求多重集的求多重集的r-組合數(shù)的一般方法組合數(shù)的一般方法利用容斥原理歸為求無限重數(shù)元素的多重集計利用容斥原理歸為求無限重數(shù)元素的多重集計數(shù)問題。數(shù)問題。將計數(shù)問題轉(zhuǎn)化為較為簡單的集合的交（或者將計數(shù)問題轉(zhuǎn)化為較為簡單的集合的交（或者并）；并）；應(yīng)用容斥原理求出這些集合的交（或并）。應(yīng)用容斥原理求出這些集合的交（或并）。容斥原理應(yīng)用于排列計數(shù)n錯位排列計數(shù)：錯位排列計數(shù)： Dn=n! Dn滿足如下遞推關(guān)系: (

6、1) Dn=(n1)( Dn2+Dn1), (n=3,4,) (2) Dn=nDn1+(1)n (n=2,3,)!1)1(! 31!21! 111 (nn容斥原理應(yīng)用于排列計數(shù)n禁位排列應(yīng)用禁位排列應(yīng)用絕對禁止位置排列絕對禁止位置排列相對禁止位置排列相對禁止位置排列 11)!(1) 1(!nkknknknnQ第7章 遞推關(guān)系和生成函數(shù)n主要內(nèi)容（重點遞推關(guān)系求解）n遞推關(guān)系：特殊問題遞推關(guān)系線性齊次遞推關(guān)系求解：特征多項式方法非齊次遞推關(guān)系求解。生成函數(shù)n生成函數(shù)利用生成函數(shù)求解遞推關(guān)系特殊序列的生成函數(shù)利用生成函數(shù)計數(shù)：如多重集組合和排列。常系數(shù)線性齊次遞推關(guān)系求解n常系數(shù)線性齊次遞推關(guān)系：

7、 hn=a1hn-1+a2hn-2+akhn-k (ak0, nk)（1）方法1：求特征方程 xka1xk1a2xk2ak=0 的特征根；分互異根及重根兩種情形。（2）方法2：求生成函數(shù)形如p(x)/q(x)；生成函數(shù)的展開式，通?；癁榇鷶?shù)分式和形式：c/(1rx)t, 利用牛頓二項式展開。 非齊次線性遞推關(guān)系求解n非齊次線性遞推關(guān)系： hn=a1hn-1+a2hn-2+akhn-k+bn方法：方法：(1)求齊次關(guān)系的一般解(2)求非齊次關(guān)系的一個特解(3)將一般解和特解結(jié)合,通過初始條件確定一般解中出現(xiàn)的常系數(shù)值。第九章n知識要點：二分圖的問題模型：車-二分圖、多米若二分圖等二分圖、匹配、覆

8、蓋及M-交錯路徑等概念求最大匹配的M-交錯路徑搜索算法互異代表系統(tǒng)，成婚條件運用延遲認(rèn)可算法解決穩(wěn)定的完備婚姻問題。匹配、覆蓋及交錯路徑的關(guān)系（1）是最大匹配不存在M-交錯路徑； M-交錯路徑可以構(gòu)造邊數(shù)多于M的匹配。（2）|M|S|, M是匹配，S是覆蓋； (G)=c(G).兩個重要算法nM-交錯路徑搜索算法：判定并構(gòu)造最大匹配。n延遲認(rèn)可算法：構(gòu)造穩(wěn)定完備婚姻配對。例題選講及解答要求1、構(gòu)造1,2,8的排列，使其逆序列是2, 5, 5, 0, 2, 1, 1, 0。（10分）解答解法解法1：根據(jù)逆序列2, 5, 5, 0, 2, 1, 1, 0，執(zhí)行逆序構(gòu)造排列算法I得到： 8: 8 7: 87 6: 867 5: 8657 4: 48657 3: 486573 2: 4865723 1: 48165723 （缺構(gòu)造過程-扣5分） 因此，對應(yīng)該逆序的排列為48165723。解答解法解法2：根據(jù)逆序列2, 5, 5, 0, 2, 1, 1, 0，執(zhí)行逆序構(gòu)造排列算法II得到： （缺構(gòu)造過程-扣5分） 因此，對應(yīng)該逆序的排列為48165723。1:12:123:1234:41235:415236:41