書籍信息
書名組合數學
書號978-7-118-08922-6
作者楊雅琴等編著
出版時間2013年8月
譯者
版次1版1次
開本16
裝幀平裝
出版基金
頁數224
字數346
中圖分類157
叢書名普通高等教育“十二五”規劃教材
定價48.00
內容簡介
組合數學起源於數學遊戲，棋盤上的麥粒和Hanoi塔問題就是經典的有關組合數學的遊戲(本書4.1節中對這兩個遊戲進行了簡單介紹)。隨著科學研究的不斷發展和科學技術的不斷進步，組合數學在科學、技術、生產、管理方面的套用越來越廣泛、深入，在航天、醫學、生物學、金融學、圖形處理等領域的前沿陣地發揮著越來越重要的作用。
本書作者多年教學和研究成果的基礎上結合組合數學的基本理論，系統地介紹了組合計數、組合設計以及相關數學理論。全書分為11章，介紹了簡單排列組合與多重集的簡單排列組合、鴿巢原理和Ramsey(拉姆齊)定理、容斥原理、生成函式、遞推方程、特殊計數、Burnside(伯恩賽德)定理和Pólya(波利亞)定理、圖論、區組設計、編碼理論等內容。
本書可以作為數學、計算機科學、密碼學或其他相關專業研究生和本科生學習組合數學的教材或參考書。
目錄
緒論 1
第一篇計 數 篇
第1章排列與組合 3
1.1加法法則和乘法法則 3
1.2排列 4
1.2.1簡單排列 4
1.2.2有條件的排列 5
1.2.3圓排列 6
1.3組合 8
1.4多重集的排列 9
1.5多重集的組合 12
1.6二項式定理 14
1.6.1二項式係數 14
1.6.2組合恆等式 15
1.6.3牛頓二項式定理 15
1.7鴿巢原理 16
1.7.1鴿巢原理的簡單形式 16
1.7.2Ramsey數 18
小結 20
習題 21
第2章容斥原理 23
2.1容斥原理 23
2.2容斥原理的套用 26
2.2.1對多重集的組合進行計數 26
2.2.2錯排問題 29
2.2.3帶有禁位的錯排問題 30
小結 33
習題 34
第3章生成函式 36
3.1生成函式的性質 36
3.2指數生成函式 39
小結 40
習題 41
第4章遞推方程 42
4.1遞推關係 42
4.2利用特徵方程求解遞推方程 44
4.2.1線性遞推方程的解 44
4.2.2非線性遞推方程的解 45
4.3利用生成函式求解遞推方程 46
4.4利用矩陣的性質求解遞推方程 48
4.4.1常係數齊次遞推方程矩陣解 48
4.4.2常係數非齊次遞推方程矩陣解 50
4.4.3變係數齊次遞推方程矩陣解 52
4.4.4變係數非齊次遞推方程矩陣解 53
小結 53
習題 54
第5章特殊計數 56
5.1Fibonacci (斐波那契)數列 56
5.2Catlan數(卡特蘭數或卡塔蘭數) 57
5.3第一類Stirling數 62
5.4第二類Stirling數 67
5.5分拆數 72
5.6分裝問題 79
5.6.1相同球和相同盒子的情況 79
5.6.2相同球和不同盒子的情況 79
5.6.3不同球和相同盒子的情況 80
5.6.4不同球和不同盒子的情況 81
小結 82
習題 84
第6章Pólya計數 86
6.1關係 86
6.2群 86
6.3置換群 88
6.4Burnside(伯恩賽德)定理 88
6.5Pólya定理 91
小結 92
習題 94
第二篇圖 論 篇
第7章圖 95
7.1圖的基本概念 95
7.2圖的同構 97
7.2.1兩個無向不完全圖同構映射的求法 97
7.2.2兩個有向不完全圖同構映射的求法 103
7.2.3不完全圖的自同構 105
7.3無向圖的連通性 107
7.4有向圖的連通性 108
7.5歐拉圖 110
7.6Hamilton 圖 111
7.6.1非賦權圖Hamilton圈(路)的求法 111
7.6.2賦權圖Hamilton圈(路)的求法 115
小結 118
習題 120
第8章樹 122
8.1樹的基本概念 122
8.2最短路徑 125
8.3匹配 127
小結 131
習題 132
第9章圖的著色 134
9.1圖的色多項式 134
9.2圖的色數 137
9.3平面圖 140
9.4地圖著色 142
小結 143
習題 145
第三篇區組設計篇
第10章區組設計 147
10.1完全區組設計 147
10.1.1完全區組設計 147
10.1.2正交拉丁方 149
10.1.3用循環矩陣構建正交拉丁方 150
10.2不完全區組設計 152
10.3柯克曼女學生問題 154
10.4斯坦納三元系 156
10.5Hadamard（阿達馬）矩陣 156
10.5.1Hadamard矩陣 156
10.5.2Ryser猜想的完整證明 158
小結 160
習題 161
第11章編碼理論 162
11.1通信系統 162
11.2離散信源的度量 165
11.2.1離散信源的信息熵 166
11.2.2離散信源的聯合熵和條件熵 168
11.3離散信道的度量 170
11.4無失真信源的編碼 174
11.4.1等長碼 176
11.4.2變長碼 179
11.4.3霍夫曼（Huffman）編碼 185
11.4.4算數編碼 187
11.4.5LZ編碼 190
11.4.6遊程（RL）編碼 191
11.5有噪信道編碼 192
11.5.1有噪信道的編碼定理 192
11.5.2糾錯碼 194
11.5.3線性分組糾錯編碼 195
11.5.4二元漢明碼 199
11.5.5循環碼 199
11.5.6BCH碼 204
小結 206
習題 210
參考文獻 215
