組合數學 王祖朝 楊越峰 9787030770257 【台灣高等教育出版社】

內容簡介
組合數學的研究對象是有限或可數的離散結構或模式，其目標之一就是在給定的準則下對結構或模式進行計數和枚舉 因此，組合數學屬於離散數學的範疇，是演算法科學的數學基礎 《組合數學》主要介紹組合計數技術， 共八章，內容安排上緊緊圍繞組合數學中三大計數技術——母函數、容斥原理和Polya 計數理論展開，具體包括基本計數技術、母函數及其應用、遞推關係、特殊計數序列、容斥原理、M?bius 反演及應用、鴿巢原理、Polya計數理論，每章均配有豐富的例題和習題，部分典型的習題給出了答案和提示

精彩書評
作者幾十年教學經驗的總結

目錄

目錄
前言
符號說明
第1章 基本計數技術 1
1 1 圖的基本概念 1
1 1 1 圖的定義 1
1 1 2 圖的連通性 3
1 1 3 圖的同構 6
1 2 基本計數原理 7
1 2 1 分類計數原理 7
1 2 2 分步計數原理 10
1 2 3 對應計數原理 11
1 2 4 殊途同歸原理 13
1 3 排列的計數 14
1 3 1 排列 14
1 3 2 重複排列 15
1 3 3 重集的排列 16
1 3 4 圓排列初步 20
1 4 組合的計數 20
1 4 1 組合 21
1 4 2 重複組合 21
1 4 3 重集的組合 23
1 4 4 不相鄰的組合 24
1 5 組合數的性質 25
1 6 q多項式係數 31
1 7 排列的生成演算法 37
1 7 1 字典序法 37
1 7 2 換位生成演算法 40
1 7 3 逆序生成演算法 42
1 8 組合的生成演算法 44
1 8 1 基於二進位的演算法 44
1 8 2 字典序法 46
1 8 3 旋轉門演算法 48
1 9 映射與排列的表示 51
1 9 1 映射的表示與計數 51
1 9 2 排列的表示與計數 55
1 9 3 排列的降序集 63
1 9 4 排列的樹表示 64
1 9 5 排列的矩陣表示 67
習題 1 68
第2章 母函數及其應用 75
2 1 普通型母函數 75
2 2 指數型母函數 87
2 3 母函數的合成 99
2 4 多元母函數 112
2 5 整數的拆分 115
2 5 1 整數拆分的概念 116
2 5 2 無序拆分的表示 118
2 5 3 無序拆分與拆分數 119
2 5 4 各部分互異的拆分 124
2 5 5 受限的拆分 126
2 5 6 拆分數 p(n) 的性質 130
2 5 7 整數的完備拆分 139
習題 2 144
第 3 章 遞推關係 148
3 1 遞推關係的概念 148
3 2 線性常係數遞推關係 151
3 3 一般遞推關係 167
習題 3 176
第4章 特殊計數序列 180
4 1 Fibonacci 序列 180
4 2 Catalan 序列 182
4 3 Schr der 序列 193
4 4 Motzkin 序列 203
4 5 Stirling 序列 207
4 6 一般反演序列 217
習題 4 218
第5章 容斥原理 226
5 1 容斥原理 226
5 2 符號形式 236
5 3 禁排問題 245
5 3 1 棋盤的概念 245
5 3 2 棋盤多項式 248
5 3 3 Ferrers 棋盤 256
習題 5 258
第 6 章 M bius 反演及應用 261
6 1 問題引入 261
6 2 偏序集 263
6 3 偏序集的構造 284
6 4 關聯代數 290
6 5 M bius 反演 311
6 6 M bius 反演的應用 316
6 6 1 Bn 上的應用 316
6 6 2 Dn 上的應用 321
6 6 3 Πn 上的應用 324
6 6 4 Fnq上的應用 327
習題 6 331
第7章 鴿巢原理 334
7 1 鴿巢原理：簡單形式 334
7 2 鴿巢原理：一般形式 338
7 3 Ramsey 問題 340
7 4 Ramsey 類定理 347
習題 7 351
第8章 Polya 計數理論 353
8 1 問題引入 353
8 2 關係、群及其性質 354
8 2 1 等價關係 355
8 2 2 群的概念和性質 355
8 2 3 子群及其判定 358
8 2 4 Lagrange 定理 360
8 2 5 群的同態與同構 362
8 3 置換群及其性質 363
8 4 Burnside 引理 370
8 5 Polya 定理 377
8 6 置換群的循環指數 385
8 7 Polya 定理的母函數形式 397
8 8 Polya 定理的擴展 409
8 8 1 直和上的擴展 409
8 8 2 Cartes 積上的擴展 413
8 8 3 子集集上的擴展 415
8 8 4 de Bruijn 定理 419
習題 8 440
習題答案或提示 443
參考文獻 459

精彩書摘
第1章 基本計數技術
眾所周知， 組合數學的研究對象是有限或可數的離散結構， 其研究目標之一就是在給定的準則下對結構進行計數和枚舉 為此， 組合數學中有許多技術和方法用於這兩個目的 單就計數來說， 就有許多非常精巧的計數方法， 但是排列與組合的計數是最直接和最基本的， 也是應用最為廣泛的 例如， 在古典概率論領域里的概率計算主要就是排列與組合的計算 本章主要介紹一些基本的計數原理以及排列與組合的計數和枚舉， 儘管可能有相當大的一部分內容讀者已經很熟悉， 我們仍然予以完整介紹 鑒於本書涉及的許多計數問題均與圖有關， 因此我們將在介紹這些基本的計數技術之前， 用一節的篇幅介紹圖論中關於圖的一些基本概念， 以方便讀者理解與圖相關的計數問題 建議讀者有選擇地閱讀本章內容， 特別需要關注的是一些問題的敘述方式及所使用的符號， 它們也將會頻繁地出現在本書的其餘部分
1 1 圖的基本概念
圖論中涉及許多有關圖的概念， 所以我們這裏並不打算一次性地將所有概念呈現出來， 一是內容太多， 二是沒有必要 因為我們的目的僅僅是服務於將圖作為計數對象的需要， 並不是完整介紹圖論的內容， 所以我們採用按需的策略， 先介紹一些最基本的概念， 然後在需要的時候再介紹相關內容
1 1 1 圖的定義
一個圖G由集合V及其二元子集E構成， 其中集合V稱為頂點集， V中的元素稱為頂點; 集合E稱為邊集， E中的元素稱為邊 因此， 一個圖G常用二元序偶 (V，E) 表示 對於沒有顯式給出頂點集和邊集的圖G， 常用V (G) 表示圖G的頂點集， E(G) 表示圖G的邊集 如果圖G的頂點集V是有限集， 則稱G是有限圖， 並稱頂點數jV j是圖G的階 (jV j表示集合V中的元素個數， 下同)， 而稱邊數jEj為圖G的大小 如果jV j=n， jEj=m， 則也稱圖G是一個 (n，m) 圖 如果V是無限集， 則稱G為無限圖 如果jEj=0， 則稱G為零圖; 如果jV j=0， 則稱G為空圖 兩個圖G和H相等， 記為G=H， 當且僅當V (G)=V (H)， E(G)=E(H)
如果圖G=(V，E) 的邊集E中每條邊e都有一個實數W(e) 與之關聯， 則實數W(e) 一般稱為邊e的權， 並稱圖G為賦權圖， 記為G=(V，E，W); 賦權圖也稱為網路 如果邊集E中所有邊均有方向， 則稱G是有向圖; 如果E中一部分邊有方向， 另一部分邊沒有方向， 則稱G是部分有向圖或混合圖; 如果E中所有邊均沒有方向， 則稱G是無向圖 對於有向邊e， 記為e=(u， v)， 其中u， v 2 V ; 如果e是無向邊， 則記為e=fu， vg， u， v 2 V 無論邊e是有向邊 (u， v) 還是無向邊fu， vg， 都稱邊e關聯頂點u和頂點v， 也稱頂點u和v關聯邊e 如果頂點u和v關聯同一條邊e， 則稱頂點u和v是相鄰的 如果兩條邊e1 和e2關聯到同一個頂點v， 則稱邊e1 和e2 是相鄰的 如果邊e關聯到同一個頂點v， 即e=(v， v) 或e=fv， vg， 則稱邊e是一個自環 如果有兩條或兩條以上的邊關聯到同一對頂點， 則稱這樣的邊為重邊 沒有重邊和自環的圖稱為簡單圖， 否則稱為重圖 如果沒有特別說明， 我們所討論的圖都是有限的簡單無向圖 在不至於混淆的情況下， 為了簡便， 我們將邊e=fu， vg或e=(u， v) 簡記為uv
設G=(V，E) 是無向圖， 對於v 2 V ， 與頂點v鄰接的頂點集合稱為頂點v的鄰域， 記為N(v); 有時我們也記為NG(v)， 以強調是圖G中的頂點 有時也用N[v]和NG[v] 來表示包含頂點v自身的鄰域， 即N[v]=N(v) [ fvg， NG[v]=NG(v) [fvg 頂點v所關聯的邊數稱為頂點v的度， 記為deg(v)， 即deg(v)=jN(v)j 如果， vng， 則稱fdeg(vi)gni=1 為圖G的度序列 可通過選擇頂點的編號， 使得度序列呈遞增或遞減的序列 對於有向圖G， 從頂點v引出的邊數稱為頂點v的出度， 記為deg (v); 而進入頂點v的邊數稱為頂點v的入度， 一般記為deg+(v)， 並以入度deg+(v) 和出度deg (v) 之和作為頂點v的度， 即deg(v)=deg+(v) + deg (v) 圖G中所有頂點度的最小值記為 δ(G)， 最大值則記為 Δ(G) 度為零的頂點稱為孤立頂點 零圖中的每個頂點都是孤立頂點 對於某個正整數k， 如果 δ(G)=Δ(G)=k， 即圖G中每個頂點的度均為k， 則稱圖G是k正則圖
對於簡單圖， 無論是有向圖還是無向圖， 其中的每條邊對頂點度的貢獻都是 2 因此， 下面的結論是顯然的， 並且一般將其稱為圖論定理
定理 1 1 設G=(V，E) 是一個簡單圖 (有向或無向)， 那麼有
這個定理有時也稱為握手定理， 意思是指在任何會議上所有人的握手次數之和為偶數， 也意味著任何圖中度為奇數 (奇度頂點) 的頂點數為偶數 對於一個 (n，m) 圖G， 根據握手定理可得
1 1 2 圖的連通性
設G=(V，E) 是一個簡單無向圖， 且jV j=n， 如果V中的任何兩個頂點都有一條邊關聯， 則稱G是一個n階完全圖， 一般記為Kn; n階零圖記為Nn 在簡單圖G中， 始於頂點v0 終於vk的頂點與邊的交錯序列， 其中的邊ei (1 i k) 關聯頂點vi 1 與vi， 則稱Wk為一條從v0 到vk的道路， 簡記為v0 vk道路， 其中k稱為道路的長度， 即道路的長度就是道路中包含的邊的條數 顯然， 一條v0 至vk長度為k的v0 vk道路， 也是一條vk至v0 長度為k的vk v0 道路 如果道路Wk中v0=vk， 則稱道路Wk為迴路 如果道路Wk中的諸頂點彼此不同 (因而諸邊必然不同)， 則該道路為一條簡單道路; 長度為k 1 的簡單道路記為Pk 如果Pk+1 中的頂點v0=vk， 則稱簡單道路Pk+1為一個k階環， 一般記為Ck; 如果k為奇數， 則稱Ck為奇環; 否則稱為偶環 實際上， 環就是簡單迴路 如果簡單道路Pk中的頂點集， vk 1g=V ， 則 稱簡單道路Pk為圖G中的一條Hamilton道路; 如果Hamilton道路Pk中的v0=vk 1， 則稱Pk為Hamilton迴路 如果道路Wk中的邊彼此不同， 且這些邊構成的集合， ekg=E， 則稱Wk為Euler道路; 如果Euler道路Wk中的v0=vk， 則稱Euler道路Wk為Euler迴路 圖 1 1 展示了幾個特殊圖K6， C6， P6 以及N10
圖1 1 特殊圖K6， C6， P6 以及N10
設G=(V，E) 是一個圖， 如果對於V中任何兩個頂點u和v， 均存在一條始於u終於v的u v道路， 則稱圖G是連通的; 否則稱G是非連通的 如果圖G是一個連通圖， 且jE(G)j=jV (G)j 1， 則稱圖G是一棵樹 容易看出， 樹是一個具有最少邊數的連通圖， 即如果從樹G中去掉任何一條邊e(記為G e)， 則G e不再是一個連通圖 反過來， 如果向樹G中增加任何一條邊e(記為G+e)， 則G+e中必存在環或迴路 一般在繪製樹圖時， 習慣將樹中的一個頂點v安排在最上面， 並稱其為樹根; 而將所有與v相鄰的頂點安排在v的下面， 並稱其為樹根v的孩子或後繼， 相應地稱樹根為這些孩子的父親或前