本書主要介紹生成函數(shù)的理論及其應(yīng)用,生成函數(shù)是計(jì)數(shù)組合學(xué)中的基本工具。本書共分四章,分別介紹了計(jì)數(shù),篩法,偏序集以及有理生成函數(shù)。
本書是《計(jì)數(shù)組合學(xué)》第一卷的中文版,共分為四章。第一章介紹了計(jì)數(shù)組合學(xué)的基本知識,包括生成函數(shù)、集合與重集、排列統(tǒng)計(jì)量以及組合計(jì)數(shù)的十二模式等;第二章介紹了計(jì)數(shù)組合學(xué)的篩法理論,包括容斥原理及其在限位排列問題、Ferrers棋盤問題、V-分拆以及單峰序列中的應(yīng)用,另外還有對合原理及其在行列式中的應(yīng)用;第三章介紹了偏序集理論,包括偏序集的基本概念、Mobius反演理論、二項(xiàng)型偏序集理論等。第四章介紹了有理生成函數(shù)理論,包括單變量有理冪級數(shù)、P-分拆、齊次線性Diophantine方程組和轉(zhuǎn)移矩陣法等。本書的選材幾乎覆蓋了基本計(jì)數(shù)組合學(xué)的所有理論,參考文獻(xiàn)非常翔實(shí)。特別值得一提的是,書中提供了大量的不同難度的習(xí)題,其中包括一些未解決的公開問題,可以幫助讀者更好地學(xué)習(xí)和理解相關(guān)的理論。
令人遺憾的是,一本書一經(jīng)出版并開始它自己的生命之旅,就無法再見證作者寫作過程中曾遇到的各種痛苦的選擇。面向哪類讀者?內(nèi)容能否經(jīng)得起推敲?能否得到專家的認(rèn)可?是每一本書的作者必須面對的難題。多數(shù)作者常會面對書的內(nèi)容清單陷入苦思冥想而遲遲不能落筆,這些書也許永遠(yuǎn)不為人知。事實(shí)上,此類突發(fā)奇想的作品在某些國家也能交付印刷f雖然它們也未必列入作者的出版物中)。
壓力是如此之大,選擇是如此的痛苦,以至于作者要有莫大的勇氣才能完成數(shù)學(xué)書籍的撰寫。這其中又以組合數(shù)學(xué)最為困難,即便是面向的讀者樂意閱讀且毫無偏見。一個(gè)孤立的特殊結(jié)果能否自成一節(jié)?一個(gè)應(yīng)用甚少初具雛形的新理論能否放心地插入到某一章中?作者更應(yīng)該注重什么,生動有趣還是嚴(yán)謹(jǐn)刻板;或者更應(yīng)該強(qiáng)調(diào)算法?
Richard Stanley很成功地突破了重重阻礙。他的書反駁了有人關(guān)于組合數(shù)學(xué)定理多,理論卻相對較少的看法。憑借對當(dāng)前階段熱點(diǎn)理論的睿智判斷,從拓?fù)涞接?jì)算機(jī)科學(xué),從代數(shù)到復(fù)變函數(shù),他選取各類大眾化的例子并加以融合。相信讀者永遠(yuǎn)不會對書中一個(gè)說明性的例證,或是一個(gè)不符合G.H.Hardy驚喜標(biāo)準(zhǔn)的證明感到茫然無措。
對于那些帶著組合問題來尋求我們幫助的同事,Stanley選擇的習(xí)題一定能為他們提供滿意的參考資料。最值得稱道的是,Stanley的寫作手法非常成功,使得該書十分引人人勝,每一位數(shù)學(xué)工作者都會樂于通篇閱讀。
Richard P.Sta rlley現(xiàn)任美國麻省理工學(xué)院數(shù)學(xué)系教授,是國際組合學(xué)界的領(lǐng)軍人物之一。1971年獲得美國哈佛大學(xué)博士學(xué)位,1988年當(dāng)選美國藝術(shù)與科學(xué)院院士,1995年當(dāng)選美國科學(xué)院院士。1975年獲得工業(yè)與應(yīng)用數(shù)學(xué)學(xué)會George Polya獎(jiǎng),2001年因兩卷本《計(jì)數(shù)組合學(xué)》獲得美國數(shù)學(xué)會Leroy P.Steele獎(jiǎng),2003年獲得瑞典皇家科學(xué)院Rolf Sctlock獎(jiǎng),2006年被邀請?jiān)趪H數(shù)學(xué)家大會上作一小時(shí)學(xué)術(shù)報(bào)告。
Stanley教授在組合數(shù)學(xué)及其與其它數(shù)學(xué)學(xué)科交叉的領(lǐng)域中做出很多原創(chuàng)性的研究工作。他的研究成果清晰簡明、深刻全面、極富創(chuàng)造力,促進(jìn)了數(shù)學(xué)諸多方向的決定性進(jìn)展。同時(shí),他非常注重扶持和培養(yǎng)年輕學(xué)者,由他撰寫的包括本書在內(nèi)的研究生教科書已成為同類書籍中的范本。
序
前言
譯者序
記號
第一章 什么是計(jì)數(shù)組合學(xué)
§1.1 如何計(jì)數(shù)
§1.2 集合與重集
§1.3 排列統(tǒng)計(jì)量
§1.4 十二模式
注記
參考文獻(xiàn)
關(guān)于習(xí)題的注記
習(xí)題
習(xí)題解答
第二章 篩法
§2.1 容斥
§2.2 例子和特殊情況
§2.3 限制位置的排列
§2.4 Ferrers棋盤
§2.5 V-分拆與單峰序列
§2.6 對合
§2.7 行列式
注記
參考文獻(xiàn)
習(xí)題
習(xí)題解答
第三章 偏序集
§3.1 基本概念
§3.2 從已知偏序集構(gòu)造新偏序集
§3.3 格
§3.4 分配格
§3.5 分配格中的鏈
§3.6 局部有限偏序集的關(guān)聯(lián)代數(shù)
§3.7 Mobius反演公式
§3.8 計(jì)算Mobius函數(shù)的技巧
§3.9 格及其Mobius代數(shù)
§3.10 半模格的Mobius函數(shù)
§3.11 ζ多項(xiàng)式
§3.12 秩選取
§3.13 R-標(biāo)號
§3.14 Euler偏序集
§3.15 二項(xiàng)型偏序集與生成函數(shù)
§3.16 在排列計(jì)數(shù)中的一個(gè)應(yīng)用
注記
參考文獻(xiàn)
習(xí)題
習(xí)題解答
第四章 有理生成函數(shù)
§4.1 單變量有理冪級數(shù)
§4.2 進(jìn)一步的細(xì)分
§4.3 多項(xiàng)式
§4.4 準(zhǔn)多項(xiàng)式
§4.5 P-分拆
§4.6 齊次線性Diophantine方程
§4.7 轉(zhuǎn)移矩陣法
注記
參考文獻(xiàn)
習(xí)題
習(xí)題解答
附錄 圖論術(shù)語
名詞索引
補(bǔ)充習(xí)題