組合數學及其應用
曾光等
商品描述
本書以組合數學中的存在問題和計數問題為主線展現理論之美,從滿足一定條件的排列組合的存在性入手,介紹計數方法和計數工具,將組合數學運用到與生活密切相關的網絡安全實例中,展現其應用之美。全書分為7章,介紹了排列組合概念與方法、特殊計數、母函數原理與應用、遞推關系和容斥原理計數方法,以及鴿籠原理和Polya計數定理。本書將合理分類與一一對應的思想貫穿全書,通過常見組合方法的使用呈現組合思想,力求深入淺出、通俗易懂。本書適合40至60學時課程講授,書中還設計了與應用結合的拓展閱讀,配有數字化資源,掃描二維碼可觀看學習。
目錄大綱
目錄
序
前言
第0章 引言 1
0.1 什麽是組合數學 1
0.2 組合問題舉例 2
0.2.1 配置的存在性（存在性問題） 2
0.2.2 配置的計數（計數問題） 3
0.2.3 配置的構造或分類（構造性問題） 3
0.2.4 配置的優化（優化問題） 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 一個奇怪的函數 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 集合的環狀排列 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 二項式系數與組合恆等式 29
1.4.1 二項式系數 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* 拓展閱讀——手勢密碼計數 51
習題1 52
第2章 特殊計數 55
2.1 格路徑基礎 55
2.1.1 增路 55
2.1.2 折線與T路 57
2.2 Catalan數 61
2.2.1 Catalan數的定義 61
2.2.2 更多形式模型 63
2.3 正整數的分拆 65
2.3.1 有序分拆計數公式 65
2.3.2 無序分拆與Ferrers圖 67
2.3.3 整數分拆與分配問題 71
2.4 集合分拆和第二類Stirling數 71
2.4.1 集合有序分拆 71
2.4.2 分拆的組合與解析定義 72
2.4.3 遞歸關系與計數公式 74
2.4.4 集合的分拆與分配問題 77
2.5 置換和第一類Stirling數 78
2.5.1 置換中的輪換 78
2.5.2 組合定義與解析定義 80
2.5.3 遞歸關系與計數公式 83
2.5.4 兩類Stirling數的三角矩陣 85
2.6* 拓展閱讀——格路徑及其應用 87
習題2 89
第3章 母函數 92
3.1 母函數與形式冪級數 92
3.1.1 母函數的概念 92
3.1.2 形式冪級數 93
3.1.3 閉公式 95
3.2 母函數的性質 97
3.3 普通型母函數 102
3.4 指數型母函數 110
3.5 母函數應用舉例 116
3.5.1 母函數與Stirling數 116
3.5.2 母函數與組合恆等式 120
3.6 分拆數的母函數 122
3.6.1 分拆數的母函數 122
3.6.2 分拆數的Euler公式 124
3.7* 拓展閱讀——伯努利數 128
習題3 130
第4章 遞推關系 133
4.1 基本概念與遞推關系的建立 133
4.1.1 遞推關系的基本概念 133
4.1.2 遞推關系的建立 134
4.2 常系數線性齊次遞推關系 139
4.3 常系數線性非齊次遞推關系 149
4.4 母函數法解常系數線性遞推關系 156
4.4.1 齊次線性遞推關系的求解 156
4.4.2 非齊次線性遞推關系的求解 161
4.5 其他類型遞推關系的求解 163
4.5.1 迭代法求解遞推關系 163
4.5.2 捲積型遞推關系的求解 168
4.5.3 線性常系數遞推關系組 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計數定理 245
7.1 Polya計數問題導入 245
7.2 置換群及其計數模式 247
7.2.1 群與置換群 247
7.2.2 循環與置換的性質 251
7.2.3 共軛類與循環指標多項式 255
7.3 Polya計數定理 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
序
前言
第0章 引言 1
0.1 什麽是組合數學 1
0.2 組合問題舉例 2
0.2.1 配置的存在性（存在性問題） 2
0.2.2 配置的計數（計數問題） 3
0.2.3 配置的構造或分類（構造性問題） 3
0.2.4 配置的優化（優化問題） 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 一個奇怪的函數 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 集合的環狀排列 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 二項式系數與組合恆等式 29
1.4.1 二項式系數 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* 拓展閱讀——手勢密碼計數 51
習題1 52
第2章 特殊計數 55
2.1 格路徑基礎 55
2.1.1 增路 55
2.1.2 折線與T路 57
2.2 Catalan數 61
2.2.1 Catalan數的定義 61
2.2.2 更多形式模型 63
2.3 正整數的分拆 65
2.3.1 有序分拆計數公式 65
2.3.2 無序分拆與Ferrers圖 67
2.3.3 整數分拆與分配問題 71
2.4 集合分拆和第二類Stirling數 71
2.4.1 集合有序分拆 71
2.4.2 分拆的組合與解析定義 72
2.4.3 遞歸關系與計數公式 74
2.4.4 集合的分拆與分配問題 77
2.5 置換和第一類Stirling數 78
2.5.1 置換中的輪換 78
2.5.2 組合定義與解析定義 80
2.5.3 遞歸關系與計數公式 83
2.5.4 兩類Stirling數的三角矩陣 85
2.6* 拓展閱讀——格路徑及其應用 87
習題2 89
第3章 母函數 92
3.1 母函數與形式冪級數 92
3.1.1 母函數的概念 92
3.1.2 形式冪級數 93
3.1.3 閉公式 95
3.2 母函數的性質 97
3.3 普通型母函數 102
3.4 指數型母函數 110
3.5 母函數應用舉例 116
3.5.1 母函數與Stirling數 116
3.5.2 母函數與組合恆等式 120
3.6 分拆數的母函數 122
3.6.1 分拆數的母函數 122
3.6.2 分拆數的Euler公式 124
3.7* 拓展閱讀——伯努利數 128
習題3 130
第4章 遞推關系 133
4.1 基本概念與遞推關系的建立 133
4.1.1 遞推關系的基本概念 133
4.1.2 遞推關系的建立 134
4.2 常系數線性齊次遞推關系 139
4.3 常系數線性非齊次遞推關系 149
4.4 母函數法解常系數線性遞推關系 156
4.4.1 齊次線性遞推關系的求解 156
4.4.2 非齊次線性遞推關系的求解 161
4.5 其他類型遞推關系的求解 163
4.5.1 迭代法求解遞推關系 163
4.5.2 捲積型遞推關系的求解 168
4.5.3 線性常系數遞推關系組 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計數定理 245
7.1 Polya計數問題導入 245
7.2 置換群及其計數模式 247
7.2.1 群與置換群 247
7.2.2 循環與置換的性質 251
7.2.3 共軛類與循環指標多項式 255
7.3 Polya計數定理 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
-cover](https://cf-assets2.tenlong.com.tw/products/images/000/181/659/medium/9786263273344.jpg?1662023002)
