組合數學及應用

劉關俊，男，教授，博士生導師。2011年獲得同濟大學計算機軟件與理論專業博士學位，同年赴新加坡科技設計大學從事博士後研究工作；2013年回國，並進入同濟大學計算機科學系任教，同年獲得德國洪堡基金資助，赴柏林洪堡大學從事博士後研究工作。 主要從事形式化方法、模型檢測、Petri網等方面的理論與應用研究，目前也從事機器學習及其在網絡交易欺詐檢測方面的研究。已出版學術專著1本，發表學術論文90餘篇，包括Science China Information Sciences、ACM Transactions on Embedded Computing Systems、ACM Transactionson Cyber-Physical Systems、IEEE Transactions on Services Computing、IEEE Transactions on Industrial Informatics等期刊論文近50篇，以及國際Petri網年會（International Conference on Application and Theory of Petri Nets and Concurrency）等會議論文40餘篇。 劉關俊主持國家自然科學基金面上項目與青年基金項目、上海市曙光計劃人才項目、中央高校交叉項目（重大）等多項，獲得國家科技進步獎二等獎、上海市科技進步獎一等獎、中國電子學會自然科學一等獎、吳文俊人工智能技術發明獎一等獎、上海市優秀博士論文獎以及首屆教育部國務院學位委員會博士研究生學術新人獎等。劉關俊是中國計算機學會形式化方法專委會委員、中國自動化學會網絡信息服務專委會委員、中國人工智能學會智能空天系統專委會委員、IEEESenior Member。

目錄
第1章 排列與組合
1.1 加法原則與乘法原則 1
1.2 集合上的排列 2
1.3 集合上的組合 4
1.4 多集上的排列 6
1.5 多集上的組合 9
1.6 應用：進程互斥建模與死鎖分析 10
習題 15
第2章 二項式定理與信息熵
2.1 二項式定理與多項式定理 19
2.2 二項式恆等式 23
2.3 二項分佈及其熵 30
2.4 應用：決策樹學習 33
習題 38
第3章 鴿巢原理
3.1 鴿巢原理的簡單形式 41
3.2 鴿巢原理的一般形式 44
3.3 應用：多索引哈希 46
習題 52
第4章 拉姆齊理論
4.1 雙色拉姆齊數 55
4.2 多色拉姆齊數 64
4.3 廣義拉姆齊數 67
4.4 應用：香農容量 70
習題 73
第5章 生成函數
5.1 生成函數的定義與運算 75
5.2 一些簡單的生成函數 80
5.3 應用：概率分佈的期望與方差 83
習題 87
第6章 遞歸關系
6.1 常系數線性齊次遞歸關系 89
6.2 基於生成函數求解遞歸關系 95
6.3 斐波那契數及其遞歸關系 98
6.4 卡特蘭數及其遞歸關系 100
6.5 斯特林數及其遞歸關系 103
6.6 調和數及其遞歸關系 109
6.7 應用：快速排序 110
習題 112
第7章 容斥原理
7.1 容斥原理的簡單形式 115
7.2 容斥原理的一般形式 119
7.3 棋子多項式 122
7.4 莫比烏斯反演 132
7.5 應用：非對稱旅行商問題 138
習題 143
第8章 伯恩賽德計數定理和波利亞計數定理
8.1 置換群 145
8.2 伯恩賽德計數定理 148
8.3 波利亞計數定理 152
8.4 應用：門電路等價類問題 154
習題 156
參考文獻 159
附錄符號表 165
索引 167