應用組合數學

譯者序
前言
記號
第1章　什麼是組合數學
　1.1　組合數學的三個問題
　1.2　組合數學的歷史和應用
　練習
　參考文獻
第一部分　組合數學的基本工具
　第2章　基本計數規則
　　2.1　乘法規則
　　2.2　加法規則
　　2.3　排列
　　2.4　計算的復雜度
　　2.5　r排列
　　2.6　子集
　　2.7　r組合
　　2.8　概率
　　2.9　放回取樣
　　2.10　分裝問題
　　　2.10.1　分裝問題的類型
　　　2.10.2　情況1︰可區分球和可區分盒子
　　　2.10.3　情況2︰不可區分球和可區分盒子
　　　2.10.4　情況3︰可區分球和不可區分盒子
　　　2.10.5　情況4︰不可區分球和不可區分盒子
　　　2.10.6　例子
　　2.11　多項式系數
　　　2.11.1　帶有特殊分配的分裝問題
　　　2.11.2　帶有不可區分對象類的排列
　　2.12　黴的完全分解
　　2.13　再論帶有不可區分對象類的排列
　　2.14　二項式展開
　　2.15　簡單游戲中的勢力
　　　2.15.1　簡單游戲的例子
　　　2.15.2　Shapley-Shubik勢力指數
　　　2.15.3　聯合國安理會
　　　2.15.4　兩院制立法機構
　　　2.15.5　成本分攤
　　　2.15.6　特征函數
　　2.16　生成排列和組合
　　　2.16.1　生成排列的算法
　　　2.16.2　生成集合子集的算法
　　　2.16.3　生成組合的算法
　　2.17　排列間的倒位距離和突變研究
　　2.18　好算法
　　　2.18.1　漸近分析
　　　2.18.2 NP完全問題
　　2.19　鴿巢原理及其擴展
　　　2.19.1　最簡單的鴿巢原理
　　　2.19.2　鴿巢原理的擴展和應用
　　　2.19.3　拉姆齊數
　　附加練習
　　參考文獻
　第3章　圖論概述
　　3.1　基本概念
　　　3.1.1　一些例子
　　　3.1.2　有向圖和圖的定義
　　　3.1.3　標簽有向圖和同構問題
　　3.2　連通性
　　　3.2.1　有向圖中的可達性
　　　3.2.2　圖中的連通性
　　　3.2.3　強連通有向圖和連通圖
　　　3.2.4　子圖
　　　3.2.5　連通分支
　　3.3　圖著色及其應用
　　　3.3.1　一些應用
……
　第4章　關系
第二部分 計數問題
　第5章 生成函數及其應用
　第6章 遞推關系
　第7章 容斥原理
　第8章 波利亞計數理論
第三部分 存在問題
　第9章 組合設計
　第10章 編碼理論
　第11章 圖論中的存在問題
第四部分 組合優化
　第12章 匹配與覆蓋
　第13章 圖和網絡的優化問題

本書以組合數學的實際應用為背景，非常全面地講述了組合數學的基本知識和基本問題，以及這些知識在計算機科學、密碼學、政治經濟學、生物學1醫學、遺傳學等各個領域的實際應用。

本書分四個部分。第一部分講述組合數學的基本工具，而其余三個部分分別講述組合數學的三個基本問題︰計數問題、存在問題和優化問題。各章以實際應用為例，引出該章的主要課題，然後對前後關聯的知識點逐步展開討論，在討論中又提出更多的示例，力圖讓讀者掌握所講述的思想並靈活運用相關的方法，另外，各節給出很多相關的練習，使讀者能夠檢驗所學知識，同時引人新概念和新應用，為讀者靈活運用書中的組合技術提供素材。因此，本書的一大特點就是包含大量的實際例子及練習，其中許多例子和練習都來自于最新的文獻，這些例子和練習前後呼應、反復出現，形成若干系列，可以看出經過了作者的精心篩選。

本書的另一個特點是強調算法。當今計算機的快速發展和各種算法的開發是促進組合數學快速發展和廣泛應用的主要動力之一，而組合數學的快速發展同樣促進了計算機理論的發展及計算機在各個領域的廣泛應用。所以，組合數學與計算機科學之間已經形成了密不可分的關系，組合數學是計算機科學——特別是計算機算法的基礎。現在，組合數學已經成為多數大學計算機專業研究生的必修課程。

本書的第三個特點是，不僅給出了絕大多數結果的嚴密證明，而且不拘泥于通常教科書所用的概念和結果，對一些概念和結果進行了擴展。

本書可以作為計算機專業和數學專業高年級本科生或研究生的教材，也可以作為相關科研人員的參考書，不滿足于“離散數學”課程所學內容的學生可以通過本書繼續自學，而本書各章後的參考文獻則為希望繼續深人學習、了解科研前沿及應用前沿的讀者提供了參考。

在翻譯本書時，我們遇到了許多不同專業的術語。我們力圖使術語簡單、易懂，一些術語沒有采用數學專業的說法，而是采用計算機科學專業的說法。對于中文特別難以反映其本質內容的術語，我們采取了不譯的做法，由于書中涉及應用的多樣性和譯者的水平所限，難免有不當之處，敬請讀者批評指正。