计数组合学导引

前言

序

致谢

第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 性质B

6.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 强归纳

参考文献

索引

常用记号

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.

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