計數(shù)組合學導(dǎo)引

前言

What could be a more basic mathematical activity than counting thenumber of elements of a finite set？The misleading simplicity that definesthe subject of enumerative combinatorics iS in fact one of its principalcharms．Who would suspect the wealth of ingenuity and of．sophisticatedtechniques that can be brought to bear on a such an apparently superficialendeavor？Mikl6s B6na has done a masterful iob of bringing an overviewof a11 of enumerative combinatorics within reach of undergraduates．Thetwo fundamental themes of bijective proofs and generating functions，to-gether with their intimate connections，recur constantly．A wide selectionof topics，including several never appearing before in a textbook，are in-cluded that give an idea of the vast range of enumerative combinatorics．In particular，for those with sufficient background in undergraduate lin-ear algebra and abstract algebra there are many tantalizing hints of thefruitful connection between enumerative combinatorics and algebra thaltplays a central role in the subject of algebraic combinatorics．In a fore-word to another book by Mikl6s B6na 1 wrote，“This book can be utilizedat a variety of levels，from random samplings of the treasures therein to acomprehensive attempt to master all the material and solve all the exer-cises．In whatever direction the reader’S tastes lead，a thorough enjoymentand appreciation of a beautiful area of combinatorics iS certain to ensue．”Exactly the same sentiment applies to the present book，as the reader willsoon discover．

內(nèi)容概要

　　The book can be used in at least three ways. One can teach a onesemester course from it， choosing the most general topics. One can alson use the book for a two-semester course， teaching most of the text and exploring the supplementary material that is given in form of exercises.If one has already taught a one-semester course using a general Combi-natorics textbook and wants to follow up with a second semester that focuses on enumeration， one may use the last six chapters of this book.The book is also useful for teaching an introductory course for graduate students who do not have solid background in Combinatorics.　　There are several topics here that are discussed in detail in an under-graduate textbook for a first time， such as acyclic and parking functions，unimodality， log-concavity， the real zeros property， and magic squares.Therefore， we hope the book will provide a useful reference material for students interested in these topics.

作者簡介

作者：(匈牙利)Miklos Bona

書籍目錄

前言序致謝第1章 基本方法1.1 何時用加法，何時用減法1.1.1 何時用加法1.1.2 何時用減法1.2 何時用乘法1.2.1 乘法原理1.2.2 聯(lián)合使用幾個計數(shù)原理1.2.3 何時不允許有重復(fù)1.3 何時用除法1.3.1 除法原理1.3.2 子集1.4 基本計數(shù)原理的應(yīng)用1.4.1 雙射的證明1.4.2 項式系數(shù)的性質(zhì)1.4.3 有重排列1.5 鴿巢原理評注小結(jié)練習題習題解答補充習題第2章 基本方法的直接應(yīng)用2.1 多重集與合成2.1.1 弱合成2.1.2 合成2.2 集合的劃分2.2.1 第二類斯特林數(shù)2.2.2 第二類斯特林數(shù)的遞推關(guān)系2.2.3 何時塊的數(shù)量是不固定的2.3 整數(shù)的分拆2.3.1 整數(shù)的非增有限序列2.3.2 法勒斯圖樣及其應(yīng)用2.3.3 嘗試一下：歐拉五角形數(shù)定理2.4 容斥原理2.4.1 兩個相交的集合2.4.2 三個相交的集合2.4.3 任意多個相交的集合2.5 放球入箱的12類方式評注小結(jié)練習題習題解答補充習題第3章 母函數(shù)3.1 冪級數(shù)3.1.1 廣義二項式系數(shù)3.1.2 形式冪級數(shù)3.2 輕松一刻：解遞推關(guān)系式3.2.1 通常母函數(shù)3.2.2 指數(shù)型母函數(shù)3.3 母函數(shù)的積3.3.1 通常母函數(shù)3.3.2 指數(shù)型母函數(shù)3.4.嘗試一下：兩個母函數(shù)的復(fù)合3.4.1 通常母函數(shù)3.4.2 指數(shù)型母函數(shù)3.5 嘗試一下：母函數(shù)的不同形式評注小結(jié)練習題習題解答補充習題第4章 排列的計數(shù)4.1 歐拉數(shù)4.2 排列的循環(huán)結(jié)構(gòu)4.2.1 第一類斯特林數(shù)4.2.2 給定類型的排列4.3 循環(huán)結(jié)構(gòu)和指數(shù)型母函數(shù)4.4 逆序4.4.1 關(guān)于逆序排列的計數(shù)評注小結(jié)練習題習題解答補充習題第5章 圖的計數(shù)5.1 樹和森林的計數(shù)5.1.1 樹的計數(shù)5.2 圖同構(gòu)5.3 標號頂點樹的計數(shù)5.3.1 森林的計數(shù)5.4 圖和函數(shù)5.4.1 非循環(huán)函數(shù)5.4.2 停車函數(shù)5.5 何時頂點不能自由標號5.5.1 有根平面樹5.5.2 二叉平面樹5.6 嘗試一下：著色頂點圖5.6.1 色多項式5.6.2 k色圖的計數(shù)5.7 圖和母函數(shù)5.7.1 樹的母函數(shù)5.7.2 連通圖的計數(shù)5.7.3 歐拉圖的計數(shù)評注小結(jié)練習題習題解答補充習題第6章 極值組合學6.1 極圖理論6.1.1 二部圖6.1.2 圖蘭定理6.1.3 無圈圖6.1.4 無完全二部圖的圖6.2 超圖6.2.1 具有分段相交邊的超圖6.2.2 具有分段不可比邊的超圖6.3 沒有的反面：存在性證明6.3.1 性質(zhì)B6.3.2 排除單色等差數(shù)列6.3.3 有限字母表組成的代碼評注小結(jié)練習題習題解答補充習題第7章 對稱結(jié)構(gòu)7.1 具有對稱性的超圖7.2 有限投影平面7.2.1 嘗試一下：質(zhì)數(shù)冪階的有限投影平面7.7 糾錯碼7.3.1 字的區(qū)分7.3.2 由超圖得到的碼7.3.3 完滿碼7.4 對稱結(jié)構(gòu)的計數(shù)評注小結(jié)練習題習題解答補充習題第8章 組合學中的序列8.1 單峰性8.2 對數(shù)凹性8.2.1 對數(shù)凹性蘊含著單峰性8.2.2 積性質(zhì)8.2.3 內(nèi)射的證明8.3 實零點性質(zhì)評注小結(jié)練習題習題解答補充習題第9章 幻方和幻立方的計數(shù)9.1 一個有趣的分布問題9.2 固定規(guī)模的幻方9.2.1 n=3的情形9.2.2 對固定n的廳Hn(r)函數(shù)9.3 固定線和的幻方9.4 為什么幻立方就不同了評注小結(jié)練習題習題解答補充習題附錄A數(shù)學歸納法A.1 弱歸納A.2 強歸納參考文獻索引常用記號

章節(jié)摘錄

插圖：Assume we want to send a message from our cell phone using justthe two-letter binary alphabet consisting of the letters 0 and 1. Say themessage that we want to send is a YES or NO message. We could agreewith the recipient that I means yes, and 0 means no. This is simple enoughif we are both sure that we will not make any mistakes in typing.However, if mistakes are possible, then this way of encoding messageswill not be efficient. Indeed, one single mistake could totally turn themeaning of the message into its opposite. One way to make sure thatour message is not misunderstood is to send it over and over again, inconsecutive bits. Say that we will send our message three times. If themessage is YES, then we will send the digits 111, and if the messageis NO, then we will send the digits 000. These two codewords are notat all similar to each other. Therefore, if we are sure that at most onetyping mistake will be made, we can rest assured that our message willbe understood properly. Indeed, if we want to send the codeword 111（resp. 000）, and at most one mistake will be made, then the receivedword will contain at least two ls （resp. at least two 0s）. So as long as atmost one bit is erroneous in each codeword, all errors can be corrected.This simple example can be generalized in many different directions.First, it could be that there are more than just two possible messagesto send. Second, it could also be that there are more than two digits inour coding alphabet. Third, more than one mistake may be made duringtyping. Nevertheless, the main idea of our simple example is crucial. Thisidea is that if the codewords are sufficiently dissimilar from each other,then we can teU them apart even if a few mistakes are made. It is time that we made the notions of "sufficiently dissimilar" and "few mistakes" more precise.

媒體關(guān)注與評論

Mikl6s B6na has done a masterful job of bringing an overview of all of enumerativecombinatorics within reach of undergraduates. The two fundamental themes ofbijective proofs and generating functions, together with their intimate connections,recur constantly. A wide selection of topics, including several never appearing beforein a textbook, are included that give an idea of the vast range of enumerativecombinatorics. In particular, for those with sufficient background in undergraduatelinear algebra and abstract algebra there are many tantalizing hints of the fruitfulconnection between enumerative combinatorics and algebra that plays a central rolein the subject of algebraic combinatorics.  　　——Richard Stanley Cambridge, Massachusetts

編輯推薦

《計數(shù)組合學導(dǎo)引》：THIS EDITION IS LICENSED FOR DISTRIBUTION AND SALE IN THEPEOPLE'S REPUBLIC OF CHINA ONLY, EXCLUDING HONGKONG,TAIWAN AND MACAU, AND MAY NOT BE DISTRIBUTED AND SOLDELSEWHERE.

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

    計數(shù)組合學導(dǎo)引 PDF格式下載

---