組合數學(第5版)（簡體書）

本書是《組合數學(第4版)》的修訂版，全書共分7章，分別是排列與組合、遞推關係與母函數、容斥原理與鴿巢原理、Burnside引理與Pólya定理、區組設計、編碼簡介和組合演算法簡介.豐富的實例及理論和實際相結合是本書一大特點，有利於對問題的深入理解.
本書是電腦相關專業本科生和研究生的教學用書，也可作為數學專業師生的教學參考書.本書封面貼有清華大學出版社防偽標籤，無標籤者不得銷售。

盧開澄，清華大學計算機系教授，長期從事組合數學、圖論、計算機算法、密碼學等課程的教學科研工作，2000-2004年曾到澳門科技大學資訊學院講授組合數學、圖論、計算機算法、密碼學、編碼理論等課程，并培養研究生。以“混合密碼”成果獲國家科技進步獎；與航空部合作的“遠程通信”加密獲國家及部級科技進步獎。著有《計算機密碼學——計算機網絡中的數據保密與安全（第３版）》、《計算機算法導引——設計與分析（第２版）》、《圖論及其應用（第2版）》、《線性規劃》等多部普通高等教育“十一五”*規劃教材。獲北京市教學成果獎兩次，清華大學先進工作者多次。

普通高等教育“十一五”*規劃教材，超經典組合數學教材，清華大學計算機系教授多年傾力打造，獲先進科技圖書獎，逾百所高校師生采用，累計發行逾15萬冊。本書的特點注重引進典型實例，深入淺出，引人入勝，可以說豐富的例子是本書的財富。全書內容包括排列與組合、遞推關系與母函數、容斥原理與鴿巢原理、Burnside引理與Pólya定理、區組設計、編碼簡介和組合算法簡介。本書內容取舍得當，理論聯系實際，特別適合作為計算機相關專業本科生和研究生的教材，也可作為數學專業師生的教學參考書。本書自出版以來，已經多次再版和重印，累計發行逾15萬冊，深受廣大師生和讀者歡迎，數百所高校選用本書作為專業課教材，普遍反映該教材特色突出，教學效果很好。

章排列與組合11.1加法法則與乘法法則11.2一一對應51.3排列與組合81.3.1排列與組合的模型81.3.2排列與組合問題的舉例91.4圓周排列141.5排列的生成算法151.5.1序數法151.5.2字典序法171.5.3換位法181.6允許重復的組合與不相鄰的組合201.6.1允許重復的組合201.6.2不相鄰的組合211.6.3線性方程的整數解的個數問題211.6.4組合的生成211.7組合意義的解釋221.8應用舉例281.9Stirling公式36*1.9.1Wallis公式36*1.9.2Stirling公式的證明38習題39第2章遞推關系與母函數432.1遞推關系432.2母函數442.3Fibonacci序列472.3.1Fibonacci序列的遞推關系472.3.2若干等式482.4優選法與Fibonacci序列的應用492.4.1優選法492.4.2優選法的步驟512.4.3Fibonacci的應用512.5母函數的性質522.6線性常系數齊次遞推關系552.7關于線性常系數非齊次遞推關系622.8整數的拆分682.9Ferrers圖像712.10拆分數估計742.11指數型母函數762.11.1問題的提出762.11.2指數型母函數的定義772.12廣義二項式定理782.13應用舉例812.14非線性遞推關系舉例1002.14.1Stirling數1002.14.2Catalan數1052.14.3舉例1092.15遞推關系解法的補充112習題114第3章容斥原理與鴿巢原理12031DeMorgan定理12032容斥定理12133容斥原理舉例1243.4棋盤多項式與有限制條件的排列1293.5有禁區的排列1323.6廣義的容斥原理1343.6.1容斥原理的推廣1343.6.2一般公式1353.7廣義容斥原理的應用1383.8第2類司特林數的展開式1413.9歐拉函數(n)1423.10n對夫妻問題1433.11Mbius反演定理1433.12鴿巢原理146313鴿巢原理舉例147314鴿巢原理的推廣1503141推廣形式之一1503142應用舉例1503.14.3推廣形式之二1553.15Ramsey數1563.15.1Ramsey問題1563.15.2Ramsey數159習題162第4章Burnside引理與Pólya定理16841群的概念168411定義168412群的基本性質16942置換群17143循環、奇循環與偶循環17544Burnside引理179441若干概念179442重要定理181443舉例說明18445Pólya定理18646舉例18847母函數形式的Pólya定理19448圖的計數197習題201第5章區組設計2035.1問題的提出2035.2拉丁方與正交的拉丁方2045.2.1問題的引入2045.2.2正交拉丁方及其性質2055.3域的概念2065.4Galois域GF(pn)2085.5正交拉丁方的構造2115.6正交拉丁方的應用舉例2135.7均衡不完全的區組設計2145.7.1基本概念2145.7.2(b,v,r,k,λ)設計2155.8區組設計的構成方法2185.9Steiner三元系220習題222第6章編碼簡介2256.1基本概念2256.2對稱二元信道2266.3糾錯碼2276.3.1近鄰法則2276.3.2Hamming不等式2286.4若干簡單的編碼2296.4.1重復碼2296.4.2奇偶校驗碼2296.5線性碼2306.5.1生成矩陣與校驗矩陣2306.5.2關于生成矩陣和校驗矩陣的定理2336.5.3譯碼步驟2336.6Hamming碼2346.7BCH碼235習題238第7章組合算法簡介2417.1歸并排序2417.1.1算法2417.1.2舉例2427.1.3復雜性分析2427.2快速排序2437.2.1算法的描述2447.2.2復雜性分析2457.3FordJohnson排序法2467.4排序的復雜性下界2487.5求第k個元素2497.6排序網絡2517.6.101原理2527.6.2Bn網絡2527.6.3復雜性分析2547.6.4Batcher奇偶歸并網絡2547.7快速傅里葉變換2557.7.1問題的提出2557.7.2預備定理2567.7.3快速算法2577.7.4復雜性分析2597.8DFS算法2607.9BFS算法2617.10αβ剪枝術2627.11狀態與圖2637.12分支定界法2657.12.1TSM問題2657.12.2任務安排問題2687.13短樹與Kruskal算法2707.14Huffman樹2707.15多段判決2727.15.1問題的提出2727.15.2佳原理2747.15.3矩陣鏈積問題2747.15.4圖的兩點間短路徑275習題276