組合數(shù)學原書第5版 布魯?shù)蟨df掃描版

組合數(shù)學原書第5版是一本計算機科學書籍，由美國威斯康星大學麥迪遜分校數(shù)學系教授布魯?shù)暇幹?。本書是系統(tǒng)闡述組合數(shù)學基礎、理論、方法和實例的優(yōu)秀教材，側重于組合數(shù)學的概念和思想，包括鴿巢原理、計數(shù)技術、排列與組合、Polya計數(shù)法、二項式系數(shù)、容斥原理、生成函數(shù)和遞推關系以及組合結構（匹配、試驗設計、圖）等，深入淺出地表達了作者對該領域全面和深刻的理解。新版本增加了有限概率、相異代表系、匹配數(shù)等內容，同時刪除若干不影響對組合數(shù)學理解的內容，或將其移作習題，以保持本書內容不致過于寵大而使讀者卻步。

內容介紹

《組合數(shù)學原書第5版》系統(tǒng)地闡述組合數(shù)學基礎、理論和方法，側重于組合數(shù)學的概念和思想，論述了鴿巢原理、排列與組合、二項式系數(shù)、容斥原理及應用、遞推關系和生成函數(shù)、特殊計數(shù)序列、二分圖中的匹配、組合設計、圖論、有向圖及網(wǎng)絡、Polya計數(shù)法等。此外，各章均包含大量練習題，并在書末給出了參考答案與提示，能夠適合作為高等院校相關專業(yè)組合數(shù)學課程的教材。

組合數(shù)學原書第5版章節(jié)目錄

第1章 什么是組合數(shù)學

1.1 例子：棋盤的完美覆蓋

1.2 例子：幻方

1.3 例子：四色問題

1.4 例子：36軍官問題

1.5 例子：最短路徑問題

1.6 例子：相互重疊的圓

1.7 例子：Nim游戲

1.8 練習題

第2章 排列與組合

2.1 四個基本的計數(shù)原理

2.2 集合的排列

2.3 集合的組合（子集）

2.4 多重集合的排列

2.5 多重集合的組合

2.6 有限概率

2.7 練習題

第3章 鴿巢原理

3.1 鴿巢原理：簡單形式

3.2 鴿巢原理：加強版

3.3 Ramsey定理

3.4 練習題

第4章 生成排列和組合

4.1 生成排列

4.2 排列中的逆序

4.3 生成組合

4.4 生成r子集

4.5 偏序和等價關系

4.6 練習題

第5章 二項式系數(shù)

5.1 帕斯卡三角形

5.2 二項式定理

5.3 二項式系數(shù)的單峰性

5.4 多項式定理

5.5 牛頓二項式定理

5.6 再論偏序集

5.7 練習題

第6章 容斥原理及應用

6.1 容斥原理

6.2 帶重復的組合

6.3 錯位排列

6.4 帶有禁止位置的排列

6.5 另一個禁止位置問題

6.6 莫比烏斯反演

6.7 練習題

第7章 遞推關系和生成函數(shù)

7.1 若干數(shù)列

7.2 生成函數(shù)

7.3 指數(shù)生成函數(shù)

7.4 求解線性齊次遞推關系

7.5 非齊次遞推關系

7.6 一個幾何例子

7.7 練習題

第8章 特殊計數(shù)序列

8.1 Catalan數(shù)

8.2 差分序列和Stirling數(shù)

8.3 分拆數(shù)

8.4 一個幾何問題

8.5 格路徑和Schroder數(shù)

8.6 練習題

第9章 相異代表系

9.1 問題表述

9.2 SDR的存在性

9.3 穩(wěn)定婚姻

9.4 練習題

第10章 組合設計

10.1 模運算

10.2 區(qū)組設計

10.3 Steiner三元系

10.4 拉丁方

10.5 練習題

第11章 圖論導引

11.1 基本性質

11.2 歐拉跡

11.3 哈密頓路徑和哈密頓圈

11.4 二分多重圖

11.5 樹

11.6 Shannon開關游戲

11.7 再論樹

11.8 練習題

第12章 再論圖論

12.1 色數(shù)

12.2 平面和平面圖

12.3 五色定理

12.4 獨立數(shù)和團數(shù)

12.5 匹配數(shù)

12.6 連通性

12.7 練習題

第13章 有向圖和網(wǎng)絡

13.1 有向圖

13.2 網(wǎng)絡

13.3 回顧二分圖匹配

13.4 練習題

第14章 Polya計數(shù)

14.1 置換群與對稱群

14.2 Burnside定理

14.3 Polya計數(shù)公式

14.4 練習題

練習題答案與提示

參考文獻

索引

原文摘錄

什么是組合數(shù)學

在生活中組合數(shù)學隨處可見。你是否曾經(jīng)遇到這樣的問題:有 n個參賽隊，每個隊只能與其他隊比賽一次，那么有多少場比賽呢?你是否曾經(jīng)想過，在用筆遍歷某個網(wǎng)絡時，在筆不離開紙且網(wǎng)絡任何一部分只能經(jīng)過一次的條件下，有多少遍歷方法呢?你是否計算過紙牌游戲中的滿堂紅的手數(shù)，以便確定滿堂紅的概率是多少呢?你是否嘗試著解決一個數(shù)獨問題呢?這些都是組合問題。正如這些例子所揭示的那樣，組合數(shù)學扎根于數(shù)學和游戲之中。過去研究過的許多問題，不論是出于娛樂還是出于美學上的需求，現(xiàn)今在純科學和應用科學領域都有著高度的重要性。今天，組合數(shù)學是數(shù)學的一個重要分支，組合數(shù)學高速成長起來的原因之一是計算機在我們的社會中起著重要的作用。因為計算機的速度不斷增加，所以它們已經(jīng)能夠處理大型問題，這在之前是不可能做到的。但是計算機不能獨立運行，它們必須按程序運行。這些程序的基礎通常是用來求解這些問題的組合數(shù)學算法。這些程序的有效性分析主要從程序的運行時間和存儲需求

等方面考慮，這其中涉及更多的組合數(shù)學思想。

組合數(shù)學持續(xù)發(fā)展的另一個原因就是它能夠運用到很多學科，而之前這些學科與數(shù)學幾平?jīng)]有關聯(lián)。因此，我們會發(fā)現(xiàn)組合數(shù)學的思想和技術不僅用于傳統(tǒng)的應用科學領域(比如說物理學)，還應用于社會科學、生物科學、信息論等領域。另外，組合數(shù)學和組合數(shù)學思想在很多數(shù)學分支中也變得越來越重要。

組合數(shù)學所關心的問題就是把某個集合中的對象排列成某種模式，使其滿足一些指定的規(guī)則。下面是兩種反復出現(xiàn)的通用問題:

排列的存在性。當我們想排列一個集合的對象使其滿足特定條件時，這樣的排列是否存在也許不是顯然的。這是最基本的問題。如果這樣的排列不總是可行的，那么我們很自然就要問，在什么樣的條件(必要條件和充分條件)下可以實現(xiàn)所望的排列。排列的列舉或分類。當指定的排列可行時，就有可能存在很多種實現(xiàn)它的方法。于是我們就要計數(shù)或分類不同類型的排列。

如果特定問題的排列數(shù)量較小，那么我們就可以列出這些排列。這里，重要的是要理解列出所有排列和確定它們的數(shù)量之間的差異。一旦這些排列被列出來，那么我們就可以對某個自然數(shù) 建立它們與整數(shù)集合《1，2，””，n》之間的一一對應，從而計數(shù)這些排列。我們的計算方法就是:1，2，3，”。然而，我們主要關心的是，對于特定類型的排列，在不列出它們的情況下確定這些排列數(shù)的技術問題。當然，這個排列數(shù)目也許非常大，以至于我們無法把它們全部列出來。

下面是另外兩種常常出現(xiàn)的組合問題。

研究已知的排列。在你完成了構建滿足特定條件的排列之后(也許這是一項困難的工作)，接下來可以研究它的性質和結構。

構造最優(yōu)排列。如果存在多個可行的排列，那么我們也許想要確定滿足某些優(yōu)化標準的排列，也就是說，在某種指定的意義下去尋找一個“最好”或者“最優(yōu)”的排列。因此，關于組合數(shù)學的一般描述也許就是，組合數(shù)學是研究離散構造的存在、計數(shù)、分析和優(yōu)化等問題的一門學科。雖然一些離散結構是無限的，但是在本書中，離散一般指的是有限。

組合數(shù)學驗證發(fā)現(xiàn)的主要工具之一是數(shù)學歸納法。歸納法是一個強大的方法，在組合數(shù)學中尤為如此。通常情況下，用數(shù)學歸納法證明一個較強的結果要比證明一個較弱的結果更為容易。雖然歸納步驟需要證明更多的東西，但歸納假設可以更強。數(shù)學歸納法的技巧是尋找假設和結論的正確平衡以便進行歸納。我們假定讀者熟悉歸納法，通讀了這本書之后，讀者會對此有更加深刻的了解。

組合問題的解決方案通?？梢允褂脤ｉT論證來獲取，有時需要結合一般理論的使用。我們不可能總是退回到公式或者已知的結果上。組合問題的一個典型的解決方法可能包含下面幾個步驟:(1)建立數(shù)學模型，(2 研究模型;(3) 計算若干小案例，樹立信心，洞察一切;(4)運用詳細的推理和巧思最終找到問題的答案。計數(shù)問題、容斥原理、鴿巢原理、遞推關系和生成函數(shù)、Burnside定理和 Polya計數(shù)公式等都是一般原理和方法的案例，我們將在后面各章陸續(xù)講解它們。然而，有時候還需要你的聰明才智，能夠看破要使用的專門方法或者公式并知道如何去運用它們。因此，在解決組合問題中經(jīng)驗是非常重要的。也就是說，一般來說用組合數(shù)學解決問題與用數(shù)學解決問題一樣，你解決的問題越多，你就越有可能解決隨后的新問題。下面我們考慮幾個組合問題的粗淺例子。前面幾個問題相對簡單，而后面幾個問題的結果曾經(jīng)是組合數(shù)學的主要成就。我們將在后續(xù)章節(jié)中更加詳細地討論其中的幾個問題。

使用說明

1、下載并解壓，得出pdf文件

2、如果打不開本文件，請務必下載pdf閱讀器

3、安裝后，在打開解壓得出的pdf文件

4、雙擊進行閱讀