組合數(shù)學(xué)

內(nèi)容概要

　　本書(shū)是系統(tǒng)闡述組合數(shù)學(xué)基礎(chǔ)、理論、方法和實(shí)例的優(yōu)秀教材，出版30多年來(lái)多次改版，被mit、哥倫比亞大學(xué)、uiuc、威斯康星大學(xué)等眾多國(guó)外高校采用，對(duì)國(guó)內(nèi)外組合數(shù)學(xué)教學(xué)產(chǎn)生了較大影響，也是相關(guān)學(xué)科的主要參考文獻(xiàn)之一。
　　本書(shū)側(cè)重于組合數(shù)學(xué)的概念和思想，論述了鴿巢原理、排列與組合、二項(xiàng)式系數(shù)、容斥原理及應(yīng)用、遞推關(guān)系和生成函數(shù)、特殊計(jì)數(shù)序列、二分圖中的匹配、組合設(shè)計(jì)、圖論、有向圖及網(wǎng)絡(luò)、polya計(jì)數(shù)法等。此外，各章均包含大量練習(xí)題，并在書(shū)末給出了參考答案與提示。
　　本書(shū)適合作為高等院校相關(guān)專(zhuān)業(yè)組合數(shù)學(xué)課程的教材。

作者簡(jiǎn)介

　　Richard A.
Brualdi　美國(guó)威斯康星大學(xué)麥迪遜分校數(shù)學(xué)系教授（現(xiàn)已退休），曾任系主任多年。他的研究方向包括組合數(shù)學(xué)、圖論、線性代數(shù)和矩陣?yán)碚?、編碼理論等。Brualdi教授的學(xué)術(shù)活動(dòng)非常豐富，擔(dān)任過(guò)多種學(xué)術(shù)期刊的主編。2000年由于在組合數(shù)學(xué)研究中所做出的杰出終身成就而獲得組合數(shù)學(xué)及其應(yīng)用學(xué)會(huì)頒發(fā)的歐拉獎(jiǎng)?wù)隆?/pre>


書(shū)籍目錄
出版者的話
譯者序
前言
第1章　什么是組合數(shù)學(xué)
　1.1　例子：棋盤(pán)的完美覆蓋
　1.2　例子：幻方
　1.3　例子：四色問(wèn)題
　1.4　例子：36軍官問(wèn)題
　1.5　例子：最短路徑問(wèn)題
　1.6　例子：相互重疊的圓
　1.7　例子：nim游戲
　1.8　練習(xí)題
第2章　排列與組合
　2.1　四個(gè)基本的計(jì)數(shù)原理
　2.2　集合的排列
　2.3　集合的組合(子集)
　2.4　多重集合的排列
　2.5　多重集合的組合
　2.6　有限概率
　2.7　練習(xí)題
第3章　鴿巢原理
　3.1　鴿巢原理：簡(jiǎn)單形式
　3.2　鴿巢原理：加強(qiáng)版
　3.3　ramsey定理
　3.4　練習(xí)題
第4章　生成排列和組合
　4.1　生成排列
　4.2　排列中的逆序
　4.3　生成組合
　4.4　生成r子集
　4.5　偏序和等價(jià)關(guān)系
　4.6　練習(xí)題
第5章　二項(xiàng)式系數(shù)
　5.1　帕斯卡三角形
　5.2　二項(xiàng)式定理
　5.3　二項(xiàng)式系數(shù)的單峰性
　5.4　多項(xiàng)式定理
　5.5　牛頓二項(xiàng)式定理
　5.6　再論偏序集
　5.7　練習(xí)題
第6章　容斥原理及應(yīng)用
　6.1　容斥原理
　6.2　帶重復(fù)的組合
　6.3　錯(cuò)位排列
　6.4　帶有禁止位置的排列
　6.5　另一個(gè)禁止位置問(wèn)題
　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　一個(gè)幾何例子
　7.7　練習(xí)題
第8章　特殊計(jì)數(shù)序列
　8.1　catalan數(shù)
　8.2　差分序列和stirling數(shù)
　8.3　分拆數(shù)
　8.4　一個(gè)幾何問(wèn)題
　8.5　格路徑和schr?der數(shù)
　8.6　練習(xí)題
第9章　相異代表系
　9.1　問(wèn)題表述
　9.2　sdr的存在性
　9.3　穩(wěn)定婚姻
　9.4　練習(xí)題
第10章　組合設(shè)計(jì)
　10.1　模運(yùn)算
　10.2　區(qū)組設(shè)計(jì)
　10.3　steiner三元系
　10.4　拉丁方
　10.5　練習(xí)題
第11章　圖論導(dǎo)引
　11.1　基本性質(zhì)
　11.2　歐拉跡
　11.3　哈密頓路徑和哈密頓圈
　11.4　二分多重圖
　11.5　樹(shù)
　11.6　shannon開(kāi)關(guān)游戲
　11.7　再論樹(shù)
　11.8　練習(xí)題
第12章　再論圖論
　12.1　色數(shù)
　12.2　平面和平面圖
　12.3　五色定理
　12.4　獨(dú)立數(shù)和團(tuán)數(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章　pólya計(jì)數(shù)
　14.1　置換群與對(duì)稱(chēng)群
　14.2　burnside定理
　14.3　pólya計(jì)數(shù)公式
　14.4　練習(xí)題
練習(xí)題答案與提示
參考文獻(xiàn)
索引


章節(jié)摘錄
版權(quán)頁(yè)：   插圖：   在生活中組合數(shù)學(xué)隨處可見(jiàn)。你是否曾經(jīng)遇到這樣的問(wèn)題：有n個(gè)參賽隊(duì)，每個(gè)隊(duì)只能與其他隊(duì)比賽一次，那么有多少場(chǎng)比賽呢？你是否曾經(jīng)想過(guò)，在用筆遍歷某個(gè)網(wǎng)絡(luò)時(shí)，在筆不離開(kāi)紙且網(wǎng)絡(luò)任何一部分只能經(jīng)過(guò)一次的條件下，有多少遍歷方法呢？你是否計(jì)算過(guò)紙牌游戲中的滿(mǎn)堂紅的手?jǐn)?shù)，以便確定滿(mǎn)堂紅的概率是多少呢？你是否嘗試著解決一個(gè)數(shù)獨(dú)問(wèn)題呢？這些都是組合問(wèn)題。正如這些例子所揭示的那樣，組合數(shù)學(xué)扎根于數(shù)學(xué)和游戲之中。過(guò)去研究過(guò)的許多問(wèn)題，不論是出于娛樂(lè)還是出于美學(xué)上的需求，現(xiàn)今在純科學(xué)和應(yīng)用科學(xué)領(lǐng)域都有著高度的重要性。今天，組合數(shù)學(xué)是數(shù)學(xué)的一個(gè)重要分支，組合數(shù)學(xué)高速成長(zhǎng)起來(lái)的原因之一是計(jì)算機(jī)在我們的社會(huì)中起著重要的作用。因?yàn)橛?jì)算機(jī)的速度不斷增加，所以它們已經(jīng)能夠處理大型問(wèn)題，這在之前是不可能做到的。但是計(jì)算機(jī)不能獨(dú)立運(yùn)行，它們必須按程序運(yùn)行。這些程序的基礎(chǔ)通常是用來(lái)求解這些問(wèn)題的組合數(shù)學(xué)算法。這些程序的有效性分析主要從程序的運(yùn)行時(shí)間和存儲(chǔ)需求等方面考慮，這其中涉及更多的組合數(shù)學(xué)思想。 組合數(shù)學(xué)持續(xù)發(fā)展的另一個(gè)原因就是它能夠運(yùn)用到很多學(xué)科，而之前這些學(xué)科與數(shù)學(xué)幾乎沒(méi)有關(guān)聯(lián)。因此，我們會(huì)發(fā)現(xiàn)組合數(shù)學(xué)的思想和技術(shù)不僅用于傳統(tǒng)的應(yīng)用科學(xué)領(lǐng)域（比如說(shuō)物理學(xué)），還應(yīng)用于社會(huì)科學(xué)、生物科學(xué)、信息論等領(lǐng)域。另外，組合數(shù)學(xué)和組合數(shù)學(xué)思想在很多數(shù)學(xué)分支中也變得越來(lái)越重要。 組合數(shù)學(xué)所關(guān)心的問(wèn)題就是把某個(gè)集合中的對(duì)象排列成某種模式，使其滿(mǎn)足一些指定的規(guī)則。下面是兩種反復(fù)出現(xiàn)的通用問(wèn)題： ?排列的存在性。當(dāng)我們想排列一個(gè)集合的對(duì)象使其滿(mǎn)足特定條件時(shí)，這樣的排列是否存在也許不是顯然的。這是最基本的問(wèn)題。如果這樣的排列不總是可行的，那么我們很自然就要問(wèn)，在什么樣的條件（必要條件和充分條件）下可以實(shí)現(xiàn)所希望的排列。 ?排列的列舉或分類(lèi)。當(dāng)指定的排列可行時(shí)，就有可能存在很多種實(shí)現(xiàn)它的方法。于是我們就要計(jì)數(shù)或分類(lèi)不同類(lèi)型的排列。 如果特定問(wèn)題的排列數(shù)量較小，那么我們就可以列出這些排列。這里，重要的是要理解列出所有排列和確定它們的數(shù)量之間的差異。一旦這些排列被列出來(lái)，那么我們就可以對(duì)某個(gè)自然數(shù)n建立它們與整數(shù)集合{1，2，…，n}之間的一一對(duì)應(yīng)，從而計(jì)數(shù)這些排列。我們的計(jì)算方法就是：1，2，3，…。然而，我們主要關(guān)心的是，對(duì)于特定類(lèi)型的排列，在不列出它們的情況下確定這些排列數(shù)的技術(shù)問(wèn)題。當(dāng)然，這個(gè)排列數(shù)目也許非常大，以至于我們無(wú)法把它們?nèi)苛谐鰜?lái)。 下面是另外兩種常常出現(xiàn)的組合問(wèn)題。 ?研究已知的排列。在你完成了構(gòu)建滿(mǎn)足特定條件的排列之后（也許這是一項(xiàng)困難的工作），接下來(lái)可以研究它的性質(zhì)和結(jié)構(gòu)。 ?構(gòu)造最優(yōu)排列。如果存在多個(gè)可行的排列，那么我們也許想要確定滿(mǎn)足某些優(yōu)化標(biāo)準(zhǔn)的排列，也就是說(shuō)，在某種指定的意義下去尋找一個(gè)“最好”或者“最優(yōu)”的排列。 因此，關(guān)于組合數(shù)學(xué)的一般描述也許就是，組合數(shù)學(xué)是研究離散構(gòu)造的存在、計(jì)數(shù)、分析和優(yōu)化等問(wèn)題的一門(mén)學(xué)科。雖然一些離散結(jié)構(gòu)是無(wú)限的，但是在本書(shū)中，離散一般指的是有限。 組合數(shù)學(xué)驗(yàn)證發(fā)現(xiàn)的主要工具之一是數(shù)學(xué)歸納法。歸納法是一個(gè)強(qiáng)大的方法，在組合數(shù)學(xué)中尤為如此。通常情況下，用數(shù)學(xué)歸納法證明一個(gè)較強(qiáng)的結(jié)果要比證明一個(gè)較弱的結(jié)果更為容易。雖然歸納步驟需要證明更多的東西，但歸納假設(shè)可以更強(qiáng)。數(shù)學(xué)歸納法的技巧是尋找假設(shè)和結(jié)論的正確平衡以便進(jìn)行歸納。我們假定讀者熟悉歸納法，通讀了這本書(shū)之后，讀者會(huì)對(duì)此有更加深刻的了解。 組合問(wèn)題的解決方案通常可以使用專(zhuān)門(mén)論證來(lái)獲取，有時(shí)需要結(jié)合一般理論的使用。我們不可能總是退回到公式或者已知的結(jié)果上。組合問(wèn)題的一個(gè)典型的解決方法可能包含下面幾個(gè)步驟：（1）建立數(shù)學(xué)模型；（2）研究模型；（3）計(jì)算若干小案例，樹(shù)立信心，洞察一切；（4）運(yùn)用詳細(xì)的推理和巧思最終找到問(wèn)題的答案。計(jì)數(shù)問(wèn)題、容斥原理、鴿巢原理、遞推關(guān)系和生成函數(shù)、Burnside定理和Polya計(jì)數(shù)公式等都是一般原理和方法的案例，我們將在后面各章陸續(xù)講解它們。然而，有時(shí)候還需要你的聰明才智，能夠看破要使用的專(zhuān)門(mén)方法或者公式并知道如何去運(yùn)用它們。因此，在解決組合問(wèn)題中經(jīng)驗(yàn)是非常重要的。也就是說(shuō)，一般來(lái)說(shuō)用組合數(shù)學(xué)解決問(wèn)題與用數(shù)學(xué)解決問(wèn)題一樣，你解決的問(wèn)題越多，你就越有可能解決隨后的新問(wèn)題。 下面我們考慮幾個(gè)組合問(wèn)題的粗淺例子。前面幾個(gè)問(wèn)題相對(duì)簡(jiǎn)單，而后面幾個(gè)問(wèn)題的結(jié)果曾經(jīng)是組合數(shù)學(xué)的主要成就。我們將在后續(xù)章節(jié)中更加詳細(xì)地討論其中的幾個(gè)問(wèn)題。




編輯推薦
《組合數(shù)學(xué)(原書(shū)第5版)》出版三十多年來(lái)多次改版，被MIT、哥倫比亞大學(xué)、UIUC、威斯康星大學(xué)等眾多國(guó)外高校采用，對(duì)國(guó)內(nèi)外組合數(shù)學(xué)教學(xué)產(chǎn)生了較大影響，也是相關(guān)學(xué)科的主要參考文獻(xiàn)之一。





圖書(shū)封面



圖書(shū)標(biāo)簽Tags
無(wú)




評(píng)論、評(píng)分、閱讀與下載



還沒(méi)讀過(guò)(93)
勉強(qiáng)可看(673)
一般般(114)
內(nèi)容豐富(4764)
強(qiáng)力推薦(390)


 


    組合數(shù)學(xué) PDF格式下載