本書系統(tǒng)介紹了組合數(shù)學(xué)的基本理論和計(jì)數(shù)方法,包括鴿巢原理、包含排斥原理、遞推關(guān)系、生成函數(shù)、Polya定理等,同時(shí)還討論了動(dòng)態(tài)規(guī)劃、回溯和啟發(fā)式算法等重要的組合算法。書后附有部分習(xí)題的提示或解答。
此書適合于自學(xué)青年閱讀,并且可供高校計(jì)算機(jī)專業(yè)或數(shù)學(xué)專業(yè),運(yùn)籌專業(yè)的學(xué)生及有關(guān)科技工作者參考。
第一章 引言
習(xí)題
第二章 鴿巢原理和Ramsey定理
1 鴿巢原理的簡(jiǎn)單形式及其應(yīng)用
2 鴿巢原理的加強(qiáng)形式
3 Ramsey定理
習(xí)題二
第三章 排列和組合
1 加法法則和乘法法則
2 集合的排列和組合
3 多重集的排列和組合
習(xí)題三
第四章 二項(xiàng)式系數(shù)
1 二項(xiàng)式定理
2 組合恒等式
3 非降路徑問題
4 牛頓二項(xiàng)式定理
5 多項(xiàng)式定理
習(xí)題四
第五章 包含排斥原理
1 包含排斥原理
2 多重集的r-組合數(shù)
3 錯(cuò)位排列
4 有限制條件排列問題
5 有禁區(qū)的排列問題
習(xí)題五
第六章 遞推關(guān)系
1 Fibonacci數(shù)列
2 常系數(shù)線性齊次遞推關(guān)系的求解
3 常系數(shù)線性非齊次遞推關(guān)系的求解
4 用迭代和歸納法求解遞推關(guān)系
習(xí)題六
第七章 生成函數(shù)
1 生成函數(shù)的定義及性質(zhì)
2 多重集的r-組合數(shù)
3 用生成函數(shù)來求解遞推關(guān)系
4 正整數(shù)的剖析
5 指數(shù)生成函數(shù)與多重集的排列問題
6 Catalan 數(shù)和Stirling數(shù)
習(xí)題七
第八章 Polya定理
……
第九章 動(dòng)態(tài)規(guī)劃
第十章 回溯
第十一章 啟發(fā)式算法
部分習(xí)題的解答或提示
參考書目