掃一掃
關注中圖網
官方微博
本類五星書更多>
-
>
宇宙、量子和人類心靈
-
>
氣候文明史
-
>
南極100天
-
>
考研數學專題練1200題
-
>
希格斯:“上帝粒子”的發明與發現
-
>
神農架疊層石:10多億年前遠古海洋微生物建造的大堡礁
-
>
聲音簡史
組合數學及其應用 版權信息
- ISBN：9787030750815
- 條形碼：9787030750815 ; 978-7-03-075081-5
- 裝幀：一般膠版紙
- 冊數：暫無
- 重量：暫無
- 所屬分類：>
組合數學及其應用 內容簡介
全書安排七章內容。分別為排列與組合；母函數；遞歸關系；容斥原理；鴿籠原理與Ramsey定理；Pólya計數定理；區組設計。在基本框架基礎上，補充網安特色案例，配套相應章節習題。可供大中專院校計算機、信息安全、密碼工程等相關專業本科生研究生使用，也可供相關科技工作者參考。
組合數學及其應用 目錄
目錄
序
前言
第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
展開全部
組合數學及其應用 節選
第0章引言 組合數學，又稱組合論、組合分析、組合學，在數學游戲和博弈中有它的歷史淵源，在工程學、化學、生物學、統計學、運籌學、密碼學、計算機科學等學科都有廣泛的應用.同時兼顧純粹數學和應用數學兩個領域，是組合數學的特色之一.內容的離散性、問題的趣味性、解決問題方法的多樣性，是組合數學的獨有特色. 組合數學是一個古老而又年輕的數學分支.說它古老，是因為早在4000多年前我國的“河圖洛書”的傳說就與組合數學有關，歷史上許多著名的數學難題與組合數學有關，諸如Konigsberg七橋問題、四色問題、Kirkman女學生問題、正交拉丁方問題等.這些問題吸引了一代又一代青年學子，把他們引進了組合數學研究的殿堂，使得組合數學這門學科不斷完善和發展.由于這門學科在自然科學的眾多學科里、管理科學的很多分支中及工程學的許多技術領域里，尤其在計算機科學的理論和應用上近幾十年得到迅猛飛速的發展，所以在信息時代的今天人們越來越認識到組合數學的重要性.組合數學是一塊充滿珍花異草的圣地，足以使觀賞者流連忘返，更能激發觀賞者研究的欲望和熱情. 0.1什么是組合數學 我們先舉一個典型例子來了解組合數學探討的到底是什么：把一張白紙劃分成n個區域，稱兩個區域是相鄰的如果它們有公共線段，現在把每一個區域都染上一種顏色，條件是相鄰的兩個區域都不能同色，對這n個區域染色是否用四種顏色就夠了？組合數學的問題常常是如此，先規定一件要做的事情，如用四種顏色給區域染色，這件事多半都是很容易做到，而且有各種各樣的做法，但我們同時加上了一些約束條件，如相鄰區域不得同色，情形就大不一樣了.現在有些做法符合條件有些不符合條件，我們問符合條件的做法有多少種，或者問有沒有符合條件的做法，或者要找出一種好的做法. 組合數學是研究離散結構的存在、計數、構造和優化等問題的一門學科.組合數學所研究的問題是按照一定的模式將集合的元素進行配置安排），通常反復出現的是以下四種類型的問題： （Ⅰ）配置的存在性； （Ⅱ）配置的計數或近似估計； （Ⅲ）配置的構造或分類； （Ⅳ）配置的優化. 如上述例子中集合的元素是n個區域，配置是用四種顏色染n個區域，規定的模式是相鄰的兩個區域都不能同色.當配置并非顯然存在或不存在時，首要的問題是證明或否定它的存在；當配置顯然存在或已證明存在時，需要無重復、無遺漏地求出這種配置的個數，當配置個數的計數存在困難時可對其進行近似估計，隨著計算機科學的迅猛發展，為了充分利用計算機資源，需要對配置的計數問題給出算法，因此組合數學成了算法的理論基礎；如有可能還要給出配置的構造或按照某種性質對配置進行分類.按照一定的模式將集合的元素進行配置可看作是一種組合結構，組合結構又可看作一種數學模型，社會實踐中的一些實際問題可抽象為數學模型，因此對數學模型的研究是十分有意義的.當組合結構確定后，能否進一步優化是組合優化的重要研究內容. 0.2組合問題舉例 0.2.1配置的存在性（存在性問題） 如果研究對象在滿足某些條件下才能進行下一步安排，當對象是否符合條件并非顯然存在或者顯然不存在時，首要解決的就是證明存在或者否定存在. 例如，分組密碼算法擴散層設計時，經常用到矩陣作為基本單位.設A為n階方陣，I為n階單位陣，則滿足的方陣A稱為對合矩陣.由于對合矩陣的逆矩陣就是本身，所以為了加密和解密過程的一致性，對合矩陣自然被重點關注.那么對于二元域上的n階方陣，是否一定存在對合矩陣呢？這個問題似乎容易回答，利用窮舉方法或者利用特征值構造方法可以容易構造出二元域上n階對合矩陣.但擴散層設計還有一個性質，就是要求不動點越少越好，也就是點經過矩陣乘積作用后的結果仍是該點，具有這種性質的點的數量越少越好，此時問題變成對于二元域上的n階對合矩陣，其不動點個數能否達到*低？通過下面簡單的證明，我們知道這種要求是完全不存在的. 性質0.1設A為二元域上的n階對合矩陣，則其不動點個數不小于. 證 這個性質說明二元域上的n階對合矩陣的不動點個數相當多，幾乎占空間的一半，要求同時滿足對合性質和不動點個數低，這種配置不存在.從這個例子可以看出，滿足一定條件的配置并不總是存在的，這就給我們提出了新的問題：什么條件下配置才是存在的？這就是配置的存在性研究的根本問題，有些時候這些問題的回答并不顯而易見. 0.2.2配置的計數（計數問題） 如果所要求的配置存在，則可能有多種不同的配置，這又經常給我們提出這樣的問題：有多少可能的配置方案？如何對配置方案進行合理分類？ 例如，銀行卡在操作的時候都需要輸入6位數字的口令，這里口令個數一共是106個.我們在利用RAR加密一個壓縮文檔時，同樣輸入6位口令，這時要求必須有1個小寫字母、一個大寫字母、一個特殊字符，這時可能的口令又是多少個呢？ 這個時候可以輸入的小寫字母26個，大寫字母26個，數字10個，特殊字符32個，若沒有特殊限制此時6位口令共計（26×2+10+32）6=946.加上限制之后，計數變為10×26x26×（94）3. 對于一般的計數問題，多數情形需要研究兩個配置是否屬于同一個等價數學模型，也就是先研究清楚同類配置判定的數學方法，再給出配置方案分類的計算公式.雖然任何組合問題的計數都有方法可循，但有時需要做大量研究，此時其計數的難度也是巨大的，如果問題有明顯的特解，則可以追尋特解的規律進行分類并計算出解的個數. 例如，手機的九宮格圖案解鎖總共能繪出多少種圖案？這個問題相當于把先行后列標記為1，2，3，4，5，6，7，8，9這九個數字的9個點排成3階矩陣，且合法的密碼要求如下： 密碼的長度至少為4，*長為9; 密碼中不能有重復的數字出現，比如不能同時出現兩個2; 密碼相鄰的數字必須在圖形上是相連的，這樣才符合手的滑動. 這個問題的計數就復雜得多，需要進行細致的分類研究，其*終結果是389112種，1.7節會詳細討論計算方法. 0.2.3配置的構造或分類（構造性問題） 幻方是古老且流行的數學游戲之一，一個n階幻方是由數字，構成的矩陣，滿足每行每列及兩個對角線上的元素之和均為S，這個和數S稱為幻和.因為，所以.與此相關的組合問題是確定可以構造n階幻方的n的值以及尋找構造幻方的一般方法.不難驗證不存在2階幻方，而對于其他任意的n值，都可以構造出n階幻方.容易給出3階幻方. 有很多種特殊的幻方構造方法，這里介紹delaLoubere在17世紀發現的構造方法.當n為奇數時，有一種簡單的方法來構造n階幻方.首先把1放在*上面一行的中間位置，然后按下面規則把2，3， ，n這些數字沿一條由左下至右上的斜線相鄰放置. （1）當一個數放在*上面一行的（1，k）位置，下一個數放在*下面一行的（n，k+1）位置 （2）當一個數放在*右邊一列（kn，n）位置，下一個數放在*左邊一列的（1，k-1）位置. （3）當遇到一個位置已經放置，或已經放在右上角位置，則下一個數就放在前一個數的正下方位置. 下面是一個5階幻方 1992年，丁宗智在《幻方》一書中分別介紹了奇數階、單偶數階、雙偶數階幻方的多種構造方法，而且分別給出了這三種幻方的構造模型，然后利用構造模型分別構造出相應的2k+1階、4k階、4k+2階幻方，有興趣的讀者可以參見該書. 在中國數學的發展歷程中，我們能夠看到有趣的數學、計算工具、棋類游戲都與幻方有著內在的聯系.幻方對于近代科學的發展起著很大的作用，可應用到“建路”和“Jordan曲線”等的位置解析學及組合解析學.幻方在密碼科學中也發揮著作用.例如，按幻方的置亂變換技術，可以將需保密的圖像置亂后，再按幻方原理復原，這種置亂變換可以進行多次. 0.2.4配置的優化（優化問題） 很多應用問題有多種配置方案，不同的配置方案考慮的因素和產生的結果并不完全相同，在實際中我們多希望降低因素個數并提高結果精度，這就需要在一些方案中構造或者發現一些較優的方案配置.這類都是優化問題. 0.3典型組合問題舉例 例如，在密碼算法利用MILP方法分析時，會碰到用不等式刻畫成本的問題.設n為正整數，Z2={0，1}，Z2n=Z2xZ2x xZ2為所有分量均在Z2上取值的n元組組成的集合.對任意給定集合Z2n的非空子集我們總可以用一組整系數線性不等式L完全刻畫，也就是說，該線性不等式組在限制變元取值為0和1時，其解所構成的集合恰好等于A.例如，n=3，A={（000），（101），（011），（110）}.我們可以構造一線性不等式組L: 其由4個不等式組成.容易驗證，上述線性不等式組L關于，的解集恰好為A給定上的非空子集A，求一整系數線性不等式組L，使得該線性不等式組在Z2n上的解集恰好等于4且要求L中不等式個數盡可能少.當集合A規模增大時，不等式組L并不容易發現，可以用邏輯條件模型和凸閉包的方法進行優化. 本書作為組合數學的基礎教材，只涉及前三類問題，并且以計數方法為重點介紹組合數學的基本理論和方法，重點介紹數學歸納法、迭代方法、一一對應方法、組合含義法等基本計數方法.關于上面提到的優化問題，有興趣的讀者可以參考運籌學方面的教材. 0.3典型組合問題舉例 0.3.1棋盤的完全覆蓋 考慮一個8x8的棋盤，假設有足夠多的形狀相同的骨牌，骨牌的大小恰好能蓋住棋盤的兩方格.是否能用32張骨牌蓋住棋盤的64個方格？如果能，稱這樣的配置為棋盤的完全覆蓋.一般地，當m和n為何值時，mxn的棋盤能完全覆蓋？ 0.3.2Konigsberg七橋問題 Konigsberg這座城市被河流劃分為A，B，C，D四區，有七座橋連接這四個區.問能否從某一區出發，每一座橋經過一次且僅一次回到原區（圖0.1）? 0.3.3四色猜想 在組合數學（圖論）中，也許是在全部數學中，*出名的沒有（用數學方法）解決的問題是著名的四色猜想.1872年，著名數學家凱利正式向數學學會提出四色猜想問題，從此四色猜想席卷全球，吸引了大量的數學家為之癡迷.任何一個數學家可以在五分鐘之內將這個非凡的問題（也稱為四色問題）向馬路上的任何一個普通人講清楚.在講清楚之后，雖然兩個人都懂得了這個問題，但是要想解決它卻也無能為力. 四色猜想是：“在一個平面或球面上的任何一張地圖只用四種顏色著色，使得具有一段公共邊界的兩個國家染上不同的顏色.每個國家必須由一個單連通的區域構成1976年6月，兩位數學家在兩臺不同的電子計算機上，用了1200個小時，作了100億個判斷，結果沒有一張地圖是需要五色的，*終證明了四色定理，轟動了世界.當兩位數學家發表他們的研究成果后，當地的郵局在當天發出的所有郵件上都加蓋了“四色足夠”的特制郵戳，以慶祝這困擾了人們一個多世紀的難題*終得到了解決.不過該方法就像是窮舉法，姑且不論這兩位數學家是否真的窮舉了所有可能情況，相比嚴謹的理論證明，這種證明無法讓人真正信服.四色猜想的理論證明還在繼續 0.3.4 36軍官問題 有36名軍官，來自6個不同的團隊，他們有6種不同的軍銜.問能否把這36名軍官排成一個6x6的方陣，使得每行和每列都是不同團隊的軍官并且軍銜互不相同？ 這個問題是歐拉（Euler）在18世紀作為一個數學游戲提出來的.每名軍官可用一個有序對（i，j）來表示，這里i表示他的軍銜，j表示他所在的團隊，i，j=1，2， ，6.這樣36名軍官對應36個有序對⑷j）.于是上述問題可表述為：排列這36個有序對（i，j）為一個6x6方陣，使得每行和每列的有序對中**個坐標和第二個坐標上數字1，2， ，6都出現.這樣的方陣可以分成兩個6x6的
書友推薦
- >
中國歷史的瞬間
- >
有舍有得是人生
- >
羅曼·羅蘭讀書隨筆-精裝
- >
史學評論
- >
名家帶你讀魯迅:朝花夕拾
- >
詩經-先民的歌唱
- >
巴金－再思錄
- >
我與地壇
本類暢銷
