计数组合学导引

出版时间：2009-11  出版社：清华大学出版社  作者：Miklos Bona  页数：526  
Tag标签：无  

前言

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．

内容概要

　　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 联合使用几个计数原理1.2.3 何时不允许有重复1.3 何时用除法1.3.1 除法原理1.3.2 子集1.4 基本计数原理的应用1.4.1 双射的证明1.4.2 项式系数的性质1.4.3 有重排列1.5 鸽巢原理评注小结练习题习题解答补充习题第2章 基本方法的直接应用2.1 多重集与合成2.1.1 弱合成2.1.2 合成2.2 集合的划分2.2.1 第二类斯特林数2.2.2 第二类斯特林数的递推关系2.2.3 何时块的数量是不固定的2.3 整数的分拆2.3.1 整数的非增有限序列2.3.2 法勒斯图样及其应用2.3.3 尝试一下：欧拉五角形数定理2.4 容斥原理2.4.1 两个相交的集合2.4.2 三个相交的集合2.4.3 任意多个相交的集合2.5 放球入箱的12类方式评注小结练习题习题解答补充习题第3章 母函数3.1 幂级数3.1.1 广义二项式系数3.1.2 形式幂级数3.2 轻松一刻：解递推关系式3.2.1 通常母函数3.2.2 指数型母函数3.3 母函数的积3.3.1 通常母函数3.3.2 指数型母函数3.4.尝试一下：两个母函数的复合3.4.1 通常母函数3.4.2 指数型母函数3.5 尝试一下：母函数的不同形式评注小结练习题习题解答补充习题第4章 排列的计数4.1 欧拉数4.2 排列的循环结构4.2.1 第一类斯特林数4.2.2 给定类型的排列4.3 循环结构和指数型母函数4.4 逆序4.4.1 关于逆序排列的计数评注小结练习题习题解答补充习题第5章 图的计数5.1 树和森林的计数5.1.1 树的计数5.2 图同构5.3 标号顶点树的计数5.3.1 森林的计数5.4 图和函数5.4.1 非循环函数5.4.2 停车函数5.5 何时顶点不能自由标号5.5.1 有根平面树5.5.2 二叉平面树5.6 尝试一下：着色顶点图5.6.1 色多项式5.6.2 k色图的计数5.7 图和母函数5.7.1 树的母函数5.7.2 连通图的计数5.7.3 欧拉图的计数评注小结练习题习题解答补充习题第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 性质B6.3.2 排除单色等差数列6.3.3 有限字母表组成的代码评注小结练习题习题解答补充习题第7章 对称结构7.1 具有对称性的超图7.2 有限投影平面7.2.1 尝试一下：质数幂阶的有限投影平面7.7 纠错码7.3.1 字的区分7.3.2 由超图得到的码7.3.3 完满码7.4 对称结构的计数评注小结练习题习题解答补充习题第8章 组合学中的序列8.1 单峰性8.2 对数凹性8.2.1 对数凹性蕴含着单峰性8.2.2 积性质8.2.3 内射的证明8.3 实零点性质评注小结练习题习题解答补充习题第9章 幻方和幻立方的计数9.1 一个有趣的分布问题9.2 固定规模的幻方9.2.1 n=3的情形9.2.2 对固定n的厅Hn(r)函数9.3 固定线和的幻方9.4 为什么幻立方就不同了评注小结练习题习题解答补充习题附录A数学归纳法A.1 弱归纳A.2 强归纳参考文献索引常用记号

章节摘录

插图：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.

媒体关注与评论

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

编辑推荐

《计数组合学导引》：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.

用户评论 (总计1条)

•   第171页-第186页缺了，郁闷