組合數(shù)學及其應用

目錄　
序
前言　
第0章　引言　1　
0.1　什么是組合數(shù)學　1　
0.2　組合問題舉例　2　
0.2.1　配置的存在性（存在性問題）　2　
0.2.2　配置的計數(shù)（計數(shù)問題）　3　
0.2.3　配置的構(gòu)造或分類（構(gòu)造性問題）　3　
0.2.4　配置的優(yōu)化（優(yōu)化問題）　4　
0.3　典型組合問題舉例　5　
0.3.1　棋盤的完全覆蓋　5　
0.3.2　K.nigsberg七橋問題　5　
0.3.3　四色猜想　6　
0.3.4　36軍官問題　6　
0.3.5　Kirkman女學生問題　7　
0.3.6　一個奇怪的函數(shù)　7　
0.3.7　Nim取子游戲　7　
第1章　排列與組合　9　
1.1　預備知識　9　
1.1.1　集合　9　
1.1.2　映射　11　
1.1.3　重集　12　
1.1.4　四個法則　13　
1.2　排列與組合　14　
1.2.1　集合的排列　14　
1.2.2　集合的環(huán)狀排列　15　
1.2.3　重集合的排列　16　
1.2.4　集合的組合　18　
1.2.5　重集合的組合　21
1.2.6　一一對應技巧　23　
1.3　排列與組合的生成　25　
1.3.1　全排列的生成　25　
1.3.2　組合與排列的生成　28　
1.4　二項式系數(shù)與組合恒等式　29　
1.4.1　二項式系數(shù)　29　
1.4.2　Newton二項式定理　32　
1.4.3　組合恒等式　34　
1.5　分配問題　39　
1.5.1　12種分配問題　39　
1.5.2　雜類分配問題　41　
1.6　反演公式　44　
1.6.1　Mobius反演　44　
1.6.2　二項式反演　47　
1.7*　拓展閱讀——手勢密碼計數(shù)　51　
習題1　52　
第2章　特殊計數(shù)　55　
2.1　格路徑基礎　55　
2.1.1　增路　55　
2.1.2　折線與T路　57　
2.2　Catalan數(shù)　61　
2.2.1　Catalan數(shù)的定義　61　
2.2.2　更多形式模型　63　
2.3　正整數(shù)的分拆　65　
2.3.1　有序分拆計數(shù)公式　65　
2.3.2　無序分拆與Ferrers圖　67　
2.3.3　整數(shù)分拆與分配問題　71　
2.4　集合分拆和第二類Stirling數(shù)　71　
2.4.1　集合有序分拆　71　
2.4.2　分拆的組合與解析定義　72　
2.4.3　遞歸關系與計數(shù)公式　74　
2.4.4　集合的分拆與分配問題　77　
2.5　置換和第一類Stirling數(shù)　78　
2.5.1　置換中的輪換　78　
2.5.2　組合定義與解析定義　80
2.5.3　遞歸關系與計數(shù)公式　83　
2.5.4　兩類Stirling數(shù)的三角矩陣　85　
2.6*　拓展閱讀——格路徑及其應用　87　
習題2　89　
第3章　母函數(shù)　92　
3.1　母函數(shù)與形式冪級數(shù)　92　
3.1.1　母函數(shù)的概念　92　
3.1.2　形式冪級數(shù)　93　
3.1.3　閉公式　95　
3.2　母函數(shù)的性質(zhì)　97　
3.3　普通型母函數(shù)　102　
3.4　指數(shù)型母函數(shù)　110　
3.5　母函數(shù)應用舉例　116　
3.5.1　母函數(shù)與Stirling數(shù)　116　
3.5.2　母函數(shù)與組合恒等式　120　
3.6　分拆數(shù)的母函數(shù)　122　
3.6.1　分拆數(shù)的母函數(shù)　122　
3.6.2　分拆數(shù)的Euler公式　124　
3.7*　拓展閱讀——伯努利數(shù)　128　
習題3　130　
第4章　遞推關系　133　
4.1　基本概念與遞推關系的建立　133　
4.1.1　遞推關系的基本概念　133　
4.1.2　遞推關系的建立　134　
4.2　常系數(shù)線性齊次遞推關系　139　
4.3　常系數(shù)線性非齊次遞推關系　149　
4.4　母函數(shù)法解常系數(shù)線性遞推關系　156　
4.4.1　齊次線性遞推關系的求解　156　
4.4.2　非齊次線性遞推關系的求解　161　
4.5　其他類型遞推關系的求解　163　
4.5.1　迭代法求解遞推關系　163　
4.5.2　卷積型遞推關系的求解　168　
4.5.3　線性常系數(shù)遞推關系組　174　
4.5.4　錯位排列　180　
4.6　差分方程　182
4.6.1　差分　182　
4.6.2　差分表　186　
4.6.3　差分方程　189　
4.7*　拓展閱讀——遞推與分治算法　196　
習題4　197　
第5章　容斥原理　200　
5.1　容斥原理　200　
5.2　容斥原理的推廣形式　207　
5.3　應用舉例　213　
5.4*　容斥原理在RSA公鑰加密算法中的應用　217　
習題5　219　
第6章　鴿籠原理　221　
6.1　鴿籠原理的簡單形式　221　
6.2　鴿籠原理的推廣形式　224　
6.3　Ramsey定理　226　
6.4　應用舉例　234　
6.5*　Ramsey定理在通信中的應用　241　
習題6　243　
第7章　Polya計數(shù)定理　245　
7.1　Polya計數(shù)問題導入　245　
7.2　置換群及其計數(shù)模式　247　
7.2.1　群與置換群　247　
7.2.2　循環(huán)與置換的性質(zhì)　251　
7.2.3　共軛類與循環(huán)指標多項式　255　
7.3　Polya計數(shù)定理　257　
7.3.1　置換群誘導的等價關系　257　
7.3.2　Burnside定理　259　
7.3.3　Polya定理　263　
7.3.4　Polya定理的推廣　265　
7.4　應用舉例　270　
7.5*　拓展閱讀——棋盤游戲　274　
習題7　280　
參考文獻　282