組合數學

現代數學可以分為兩大類：一類是研究連續對象的，如分析、方程等，另一類就是研究離散對象的組合數學。組合數學不僅在基礎數學研究中具有極其重要的地位，在其它的學科中也有重要的應用，如計算機科學、編碼和密碼學、物理、化學、生物等學科中均有重要應用。微積分和近代數學的發展為近代的工業革命奠定了基礎。而組合數學的發展則是奠定了本世紀的計算機革命的基礎。計算機之所以可以被稱為電腦，就是因為計算機被人編寫了程序，而程序就是演演算法，在絕大多數情況下，計算機的演演算法是針對離散的對象，而不是在作數值計算。正是因為有了組合演演算法才使人感到，計算機好像是有思維的。

組合數學不僅在軟體技術中有重要的應用價值，在企業管理，交通規劃，戰爭指揮，金融分析等領域都有重要的應用。在美國有一家用組合數學命名的公司，他們用組合數學的方法來提高企業管理的效益，這家公司辦得非常成功。此外，試驗設計也是具有很大應用價值的學科，它的數學原理就是組合設計。用組合設計的方法解決工業界中的試驗設計問題，在美國已有專門的公司開發這方面的軟體。

組合數學在國外早已成為十分重要的學科，甚至可以說是計算機科學的基礎。一些大公司，如IBM，AT&T都有全世界最強的組合研究中心。Microsoft 的Bill Gates近來也在提倡和支持計算機科學的基礎研究。例如，Bell實驗室的有關線性規劃演演算法的實現，以及有關計算機網路的演演算法，由於有明顯的商業價值，顯然是沒有對外公開的。美國已經有一種趨勢，就是與新的演演算法有關的軟體是可以申請專利的。如果照這種趨勢發展，世界各國對組合數學和計算機演演算法的投入和競爭必然日趨激烈。美國政府也成立了離散數學及理論計算機科學中心DIMACS（與Princeton大學，Rutgers大學，AT&T 聯合創辦的，設在Rutgers大學），該中心已是組合數學及理論計算機科學的重要研究陣地。美國國家數學科學研究所（Mathematical Sciences Research Institute，由陳省身先生創立）在1997年選擇了組合數學作為研究專題，組織了為期一年的研究活動。日本的NEC公司還在美國的設立了研究中心，理論計算機科學和組合數學已是他們重要的研究課題，該中心主任R. Tarjan即是組合數學的權威。美國重要的國家實際室（Los Alamos國家實驗室，以造出第一顆原子彈著稱於世），從曼哈頓計劃以來一直重視應用數學的研究，包括組合數學的研究。不僅如此，該實驗室最近還在積極充實組合數學方面的研究實力。美國另外一個重要的國家實驗室Sandia國家實驗室有一個專門研究組合數學和計算機科學的機構，主要從事組合編碼理論和密碼學的研究，在美國政府以及國際學術界都具有很高的地位。

由於生物學中的DNA的結構和生物現象與組合數學有密切的聯繫，各國對生物信息學的研究都很重視，這也是組合數學可以發揮作用的一個重要領域。由於DNA就是組合數學中的一個序列結構，美國科學院院士，近代組合數學的奠基人Rota教授預言，生物學中的組合問題將成為組合數學的一個前沿領域。

傳統的計算機演演算法可以分為兩大類，一類是組合演演算法，一類是數值演演算法（包括計算數學和與處理各種信息數據有關的信息學）。近年來計算機演演算法又多了一類：那就是符號計算演演算法。吳文俊院士開創的機器證明方法就屬於符號計算，引起了國際上的高度評價，被稱為吳方法。而國際上還有專門的符號計算雜誌。符號演演算法和吳方法跟代數組合學也有十分密切的聯繫。組合數學，數值計算（包括計算數學，科學計算，非線性科學，和與處理各種信息數據有關的信息學）和統計學可能是應用最廣的數學分支，而組合數學的價值甚至不亞於統計學和數值計算。由於數學機械化近年來的發展和在計算機科學中的重要性，把數學機械化，科學計算和組合數學組合起來，就可以說是中國信息產業的基礎。組合數學家H. Wilf和D. Zeilberger1998因為在組合恆等式的機械化證明方面的成果，獲得1998年美國數學會的Steele獎。

Thomson Science公司創刊的一份電子刊物《離散數學和理論計算機科學》即是一個很好的說明。它的內容涉及離散數學和計算機科學的眾多方面。由於計算機軟體的促進和需求，組合數學已成為一門既廣博又深奧的學科，需要很深的數學基礎，逐漸成為了數學的主流分支。

除上述以外，歐洲也在積極發展組合數學，英國、法國、德國、荷蘭、丹麥、奧地利、瑞典、義大利、西班牙等國家都建立了各種形式的組合數學研究中心。近幾年，南美國家也在積極推動組合數學的研究。澳大利亞，紐西蘭也組建了很強的組合數學研究機構。值得一提的是亞洲的發達國家也十分重視組合數學的研究。日本有組合數學研究中心，並且從美國引進人才，不僅支持日本國內的研究，還出資支持美國的有關課題的研究，這樣使日本的組合數學這幾年的發展極為迅速。中國台灣、中國香港兩地也從美國引進人才，大力發展組合數學。新加坡，韓國，馬來西亞也在積極推動組合數學的研究和人才培養。台灣的數學研究中心也正在考慮把組合數學作為重點方向來發展。

如果你仔細留心一張世界地圖，你會發現用一種顏色對一個國家著色，那麼一共只需要四種顏色就能保證每兩個相鄰的國家的顏色不同。這樣的著色效果能使每一個國家都能清楚地顯示出來。但要證明這個結論確是一個著名的世界難題，1976年數學家通過計算機運算得到證明而成為四色定理，最近人們才發現了一個更簡單的證明。

由中國組合數學家管梅谷教授提出。郵遞員要穿過城市的每一條路至少一次，怎樣行走走過的路程最短？這是一個NP完全問題。由中國組合數學家管梅谷教授提出，著名組合數學家，J. Edmonds和他的合作者給出了一個解答。

有一些員工要完成一些任務。各個員工完成不同任務所花費的時間都不同。每個員工只分配一項任務。每項任務只被分配給一個員工。怎樣分配員工與任務以使所花費的時間最少？

我國古代的河洛圖上記載了三階幻方，即把從一到九這九個數按三行三列的隊行排列，使得每行，每列，以及兩條對角線上的三個數之和都是一十五。組合數學中有許多象幻方這樣精巧的結構。1977年美國旅行者1號、2號宇宙飛船就帶上了幻方以作為人類智慧的信號。（題圖）

當你裝一個箱子時，你會發現要使箱子儘可能裝滿不是一件很容易的事，你往往需要做些調整。從理論上講，裝箱問題是一個很難的組合數學問題，即使用計算機也是不容易解決的。

在中小學的數學遊戲中，有這樣一個問題，一個船夫要把一隻狼，一隻羊和一棵白菜運過河。問題是當人不在場時，狼要吃羊，羊要吃白菜，而他的船每趟只能運其中的一個。他怎樣才能把三者都運過河呢？這就是一個很典型、很簡單的組合數學問題。

假如能找到兩對夫婦（如張（男）--李（女）和趙（男）--王（女）），如果張（男）更喜歡王（女），而王（女）也更喜歡張（男），那麼這樣就可能有潛在的不穩定性。組合數學的方法可以找到一種婚姻的安排方法，使得沒有上述的不穩定情況出現（當然這只是理論上的結論）。這種組合數學的方法卻有 一個實際的用途：美國的醫院在確定錄取住院醫生時，他們將考慮申請者的志願的先後次序，同時也給申請排序。按這樣的 次序考慮出的總的方案將沒有醫院和申請者兩者同時後悔的情況。實際上，高考學生的最後錄取方案也可以用這種方法。

我們還會遇到更複雜的調度和安排問題。例如，在生產原子彈的曼哈頓計劃中，涉及到很多工序，許多人員的安排，很多元件的生產，怎樣安排各種人員的工作，以及各種工序間的銜接，從而使整個工期的時間儘可能短？這些都是組合數學典型例子。又比如，假日飯店的管理中，也嚴格規定了有關的工序，如清潔工的第一步是換什麼，清洗什麼，第二步又做什麼，總之，他進出房間的次數應該最少。既然，這樣一個簡單的工作都需要講究工序，那麼一個複雜的工程就更不用說了。

怎樣安排運輸使得庫房充分發揮作用，進一步來說，貨物放在什麼地方最便於存取（如存儲時間短的應該放在容易存取的地方）。

我們知道，用形狀相同的方型磚塊可以把一個地面鋪滿（不考慮邊緣的情況），但是如果用不同形狀，而又非方型的磚塊來鋪一個地面，能否鋪滿呢？這不僅是一個與實際相關的問題，也涉及到很深的組合數學問題。

◆組合數學還可用於金融分析，投資方案的確定，怎樣找出好的投資組合以降低投資風險。南開大學組合數學研究中心開發出了"金沙股市風險分析系統"現已投放市場，為短線投資者提供了有效的風險防範工具。

總之，組合數學無處不在，它的主要應用就是在各種複雜關係中找出最優的方案。所以組合數學完全可以看成是一門量化的關係學，一門量化了的運籌學，一門量化了的管理學。

本書是系統闡述組合數學基礎、理論、方法和實例的優秀教材，出版近30年來多次改版，被MIT、哥倫比亞大學、UIUC、威斯康星大學等眾多國外高校採用，對國內外組合數學教學產生了較大影n向，也是相關學科的主要參考文獻之一。本書側重於組合數學的概念和思想，包括鴿巢原理、計數技術、排列組合、Polya計數法、二項式係數、容斥原理、生成函數和遞推關係以及組合結構(匹配、實驗設計、圖)等，深入淺出地表達了作者對該領域全面和深刻的理解，介紹了歷史上源於數學遊戲和娛樂的大量實例，其中對Polya計數、Burnside定理等的完美處理使得不熟悉群論的學生也能夠讀懂。除包含第3版中的內容外，本版又進行了更新，增加了莫比烏斯反演(作為容斥原理的推廣)、格路徑、Schroder數等內容。此外，各章均包含大量練習題，並在書末給出了參考答案與提示。

出版者的話

專家指導委員會

譯者序

前言

第1章 什麼是組合數學

1．1 例：棋盤的完美覆蓋

1．2 例：切割立方體

1．3 例：幻方

1．4 例：四色問題

1．5 例：36軍官問題

1．6 例：最短路徑問題

1．7 例：nim取子遊戲

1．8 練習題

第2章 鴿巢原理

2．1 鴿巢原理：簡單形式

2．2 鴿巢原理：加強形式

2．3 ramsey定理

2．4 練習題

第3章 排列與組合

3．1 四個基本的計數原理

.3．2 集合的排列

3．3 集合的組合

3．4 多重集的排列

3．5 多重集的組合

3．6 練習題

第4章 生成排列和組合

4．1 生成排列

4．2 排列中的逆序

4．3 生成組合

4．4 生成卜組合

4．5 偏序和等價關係

4．6 練習題

第5章 二項式係數

5．1 pascal公式

5．2 二項式定理

5．3 一些恆等式

5．4 二項式係數的單峰性

5．5 多項式定理

5．6 牛頓二項式定理

5．7 再論偏序集

5．8 練習題

第6章 容斥原理及應用

6．1 容斥原理

6．2 具有重複的組合

6．3 錯位排列

6．4 帶有禁止位置的排列

6．5 另外的禁排位置問題

6．6 莫比烏斯反演

6．7 練習題

第7章 遞推關係和生成函數

7．1 一些數列

7．2 線性齊次遞推關係

7．3 非齊次遞推關係

7．4 生成函數

7．5 遞歸和生成函數

7．6 一個幾何的例子

7．7 指數生成函數

7．8 練習題

第8章 特殊計數序列

8．1 catalan數

8．2 差分序列和stirling數

8．3 分拆數

8．4 一個幾何問題

8．5 格路徑和schroder數

8．6 練習題

第9章 二分圖中的匹配

9．1 一般問題表述

9．2 匹配

9．3 互異代表系統

9．4 穩定婚姻

9．5 練習題

第10章 組合設計

10．1 模運算

10．2 區組設計

10．3 steiner三元系統

10．4 拉丁方

10．5 練習題

第11章 圖論導引

11．1 基本性質

11．2 歐拉跡

11．3 hamilton路徑和hamilton圈

11．4 二分多重圖

11．5 樹

11．6 shannon開關遊戲

11．7 再論樹

11．8 練習題

第12章 有向圖及網路

12．1 有向圖

12．2 網路

12．3 練習題

第13章 再論圖

13．1 色數

13．2 平面和平面圖

13．3 五色定理

13．4 獨立數和團數

13．5 連通性

13．6 練習題

第14章 polya計數法

14．1 置換群與對稱群

14．2 burnside定理

14．3 polya計數公式

14．4 練習題

練題的答案與提示

參考文獻

索引

書名：組合數學

ISBN：9787302261261

作者：周煒

定價：21元

出版日期：2011-9-1

出版社：清華大學出版社

本書是作者多年教學和研究成果的結晶，系統地研究了組合計數、組合設計以及相關數學理論。全書分為10章：集合與函數，排列組合與多項式定理，整除性理論，數論函數，不定方程，同餘式，線性遞歸方程與母函數，鴿巢原理和Ramsey（拉姆齊）定理，Burnside（伯恩賽德）引理和Pólya（波利亞）定理，相異代表組和區組設計。

本書可以作為計算機科學與技術、數學、密碼學和其他相關專業研究生和本科生的教材使用，也可作為廣大師生和工程技術人員的自學用書或參考書。

第1章集合與函數

1.1集合論基礎

1.1.1集合的基本概念

1.1.2集合的代數運算及性質

1.1.3集合的運算性質

1.2函數、置換的循環分解

1.2.1函數的基本概念和一般性質

1.2.2置換的循環分解

1.3集合的基數、對合映射不動點定理

1.4集合上的二元關係

1.4.1二元關係的基本概念

1.4.2幾種特殊的簡單二元關係

1.4.3等價關係、商集

1.5容斥原理及應用

1.5.1容斥原理

1.5.2錯位排列問題

1.5.3容斥原理應用舉例

1.6Abel恆等式

1.7習題

第2章排列組合與多項式定理

2.1排列組合及其性質

2.1.1無重複排列和無限可重複排列

2.1.2無重複組合及其性質、多項式反演定理

2.1.3無重複有序分組、無重複無序分組

2.1.4無限可重複分組、無限可重複組合、多項式定理

2.1.5有限可重複組合與有限可重複排列

2.2排列組合應用舉例

2.3Stirling公式

2.3.1Wallis公式

2.3.2Stirling公式

2.4習題

第3章整除性理論

3.1整數的整除性

3.2最大公約數和最小公倍數

3.3連分數

3.3.1實數的連分數表示

3.3.2實數的近似分數

3.3.3近似分數的既約性

*3.3.4近似分數的誤差估計

3.3.5整數線性組合ax-by=1的生成

3.4素數、二平方定理、算術基本定理

3.5習題

第4章數論函數

4.1[x]與{x}

4.2積性函數

4.3因子數τ(n)與因子和S(n)

4.4Euler函數?(n)

4.5M?bius函數和M?bius反演定理

4.5.1M?bius函數及其性質

4.5.2M?bius反演定理

4.5.3圓排列問題

4.6習題

第5章不定方程

5.1二元一次不定方程

5.2三元一次不定方程

5.3勾股數定理

5.4習題

第6章同餘式

6.1同餘式的定義與性質

6.2完全剩餘系和縮剩餘系

6.3一元一次同餘方程

6.4一元一次同餘方程和方程組、中國剩餘定理

*6.5一元多項式同餘方程

6.6習題

第7章線性遞歸方程與母函數

7.1遞歸方程

7.1.1線性遞歸方程解的結構、降階定理

7.1.2常係數齊次線性遞歸方程的通解

7.1.3常係數非齊次線性遞歸方程的求解

7.1.4線性遞歸方程求解舉例

7.2Fibonacci數列

7.2.1Fibonacci問題的求解

7.2.2Fibonacci數列的性質

7.2.3Fibonacci數列在優選法中的應用

7.3母函數及其性質

7.3.1母函數的定義

7.3.2母函數的一般性質

7.4錯位排列和禁位排列

7.4.1錯位排列問題

*7.4.2棋盤多項式與禁位排列

*7.5正整數分拆和Ferrers圖

7.5.1正整數分拆

7.5.2Ferrers圖

7.6Stirling數

7.6.1第一類Stirling數

7.6.2第二類Stirling數

7.6.3Stirling反演定理

7.7Catalan數

7.8Bernoulli數

7.9習題

第8章鴿巢原理和Ramsey定理

8.1鴿巢原理

*8.2無向完全圖的著色問題

8.3Ramsey定理

*8.4Ramsey數的性質

8.5習題

第9章Burnside引理和Pólya定理

9.1群的基本知識

9.1.1半群、亞群、元素的階

9.1.2群、陪集、Lagrange定理

9.2Burnside引理和Pólya定理

9.2.1Burnside引理

9.2.2簡化的Pólya定理

*9.2.3Pólya基本定理

9.3習題

第10章相異代表組和區組設計

10.1相異代表組

10.2公共代表組

10.3完全區組設計與拉丁方

10.4有限域基礎

10.5正交拉丁方

*10.6均衡不完全區組設計(BIBD)

10.6.1BIBD的概念

10.6.2三連組系

10.6.3對稱BIBD

10.6.4由對稱BIBD構造其他BIBD

10.7Hadamard矩陣

10.8習題

參考文獻