《計算機科學(xué)叢書:組合數(shù)學(xué)(原書第5版)》系統(tǒng)地闡述組合數(shù)學(xué)基礎(chǔ)、理論和方法,側(cè)重于組合數(shù)學(xué)的概念和思想,論述了鴿巢原理、排列與組合、二項式系數(shù)、容斥原理及應(yīng)用、遞推關(guān)系和生成函數(shù)、特殊計數(shù)序列、二分圖中的匹配、組合設(shè)計、圖論、有向圖及網(wǎng)絡(luò)、Polya計數(shù)法等。此外,各章均包含大量練習(xí)題,并在書末給出了參考答案與提示。
《計算機科學(xué)叢書:組合數(shù)學(xué)(原書第5版)》適合作為高等院校相關(guān)專業(yè)組合數(shù)學(xué)課程的教材。
本書是系統(tǒng)闡述組合數(shù)學(xué)基礎(chǔ)、理論、方法和實例的優(yōu)秀教材,出版三十多年來多次改版,被MIT、哥倫比亞大學(xué)、UIUC、威斯康星大學(xué)等眾多國外高校采用,對國內(nèi)外組合數(shù)學(xué)教學(xué)產(chǎn)生了較大影響,也是相關(guān)學(xué)科的主要參考文獻之一。
本書側(cè)重于組合數(shù)學(xué)的概念和思想,包括鴿巢原理、計數(shù)技術(shù)、排列與組合、Polya計數(shù)法、二項式系數(shù)、容斥原理、生成函數(shù)和遞推關(guān)系以及組合結(jié)構(gòu)(匹配、試驗設(shè)計、圖)等,深入淺出地表達了作者對該領(lǐng)域全面和深刻的理解。
自2004年出版第4版以來,作者又對本書進行了全面的修訂和更新,第5版增加了有限概率、相異代表系、匹配數(shù)等內(nèi)容。
Richard A.Brualdi美國威斯康星大學(xué)麥迪遜分校數(shù)學(xué)系教授(現(xiàn)已退休),曾任系主任多年。他的研究方向包括組合數(shù)學(xué)、圖論、線性代數(shù)和矩陣理論、編碼理論等。Brualdi教授的學(xué)術(shù)活動非常豐富,擔(dān)任過多種學(xué)術(shù)期刊的主編。2000年由于在組合數(shù)學(xué)研究中所做出的杰出終身成就而獲得組合數(shù)學(xué)及其應(yīng)用學(xué)會頒發(fā)的歐拉獎?wù)隆?/span>
出版者的話
譯者序
前言
第1章 什么是組合數(shù)學(xué)
1.1 例子:棋盤的完美覆蓋
1.2 例子:幻方
1.3 例子:四色問題
1.4 例子:36軍官問題
1.5 例子:最短路徑問題
1.6 例子:相互重疊的圓
1.7 例子:Nim游戲
1.8 練習(xí)題
第2章 排列與組合
2.1 四個基本的計數(shù)原理
2.2 集合的排列
2.3 集合的組合(子集)
2.4 多重集合的排列
2.5 多重集合的組合
2.6 有限概率
2.7 練習(xí)題
第3章 鴿巢原理
3.1 鴿巢原理:簡單形式
3.2 鴿巢原理:加強版
3.3 Ramsey定理
3.4 練習(xí)題
第4章 生成排列和組合
4.1 生成排列
4.2 排列中的逆序
4.3 生成組合
4.4 生成r子集
4.5 偏序和等價關(guān)系
4.6 練習(xí)題
第5章 二項式系數(shù)
5.1 帕斯卡三角形
5.2 二項式定理
5.3 二項式系數(shù)的單峰性
5.4 多項式定理
5.5 牛頓二項式定理
5.6 再論偏序集
5.7 練習(xí)題
第6章 容斥原理及應(yīng)用
6.1 容斥原理
6.2 帶重復(fù)的組合
6.3 錯位排列
6.4 帶有禁止位置的排列
6.5 另一個禁止位置問題
6.6 莫比烏斯反演
6.7 練習(xí)題
第7章 遞推關(guān)系和生成函數(shù)
7.1 若干數(shù)列
7.2 生成函數(shù)
7.3 指數(shù)生成函數(shù)
7.4 求解線性齊次遞推關(guān)系
7.5 非齊次遞推關(guān)系
7.6 一個幾何例子
7.7 練習(xí)題
第8章 特殊計數(shù)序列
8.1 Catalan數(shù)
8.2 差分序列和Stirling數(shù)
8.3 分拆數(shù)
8.4 一個幾何問題
8.5 格路徑和Schroder數(shù)
8.6 練習(xí)題
第9章 相異代表系
9.1 問題表述
9.2 SDR的存在性
9.3 穩(wěn)定婚姻
9.4 練習(xí)題
第10章 組合設(shè)計
10.1 模運算
10.2 區(qū)組設(shè)計
10.3 Steiner三元系
10.4 拉丁方
10.5 練習(xí)題
第11章 圖論導(dǎo)引
11.1 基本性質(zhì)
11.2 歐拉跡
11.3 哈密頓路徑和哈密頓圈
11.4 二分多重圖
11.5 樹
11.6 Shannon開關(guān)游戲
11.7 再論樹
11.8 練習(xí)題
第12章 再論圖論
12.1 色數(shù)
12.2 平面和平面圖
12.3 五色定理
12.4 獨立數(shù)和團數(shù)
12.5 匹配數(shù)
12.6 連通性
12.7 練習(xí)題
第13章 有向圖和網(wǎng)絡(luò)
13.1 有向圖
13.2 網(wǎng)絡(luò)
13.3 回顧二分圖匹配
13.4 練習(xí)題
第14章 Polya計數(shù)
14.1 置換群與對稱群
14.2 Burnside定理
14.3 Polya計數(shù)公式
14.4 練習(xí)題
練習(xí)題答案與提示
參考文獻
索引