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

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

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

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

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

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

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

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