组合计数笔记

前言

第1章基本计数法则与公式

1.1基本计数法则

1.2基本计数公式Ⅰ：排列组合

1.3基本计数公式Ⅱ：分配分派

1.4基本计数公式Ⅲ：映射问题

1.5计数方法与工具

第2章递归关系

2.1差分与差分表

2.2常系数线性递归关系

2.3解递归关系的例

2.4递归关系的应用

第3章母函数

3.1两类母函数

3.2母函数的有关性质

3.3母函数的应用

3.4多重集的排列组合

第4章重要的组合数

4.1二项式系数

4.2多项式系数

4.3Gauss二项式系数

4.4Fibonacci数列

4.5Catalan数

4.6Stirlin9数

4.7Lab数

第5章容斥原理及其应用

5.1容斥原理

5.2广容斥原理

5.3容斥原理的应用

5.4更列数和相邻禁位数

5.5Euler函数与MSbius函数

5.6广义MSbius反演

5.7一般限位排列与车多项式

第6章整数分拆

6.1基本概念

6.2无序分拆

6.3无序分拆的特例

6.4有序分拆

第7章Hall定理和集族的代表系

7.1背景和定义

7.2相异代表系

7.3公共代表系

7.4Hall定理的应用

7.5Hall定理的推广

第8章鸽笼原理和Ramsey理论

8.1鸽笼原理

8.2Ramsey理论

8.3几个经典定理

8.4图的Ramsey理论

第9章P61ya计数理论

9.1作用在集合上的群

9.2有关的群的运算

9.3置换群的轮换指标

9.4Burnside引理

9.5P61ya计数定理

9.6圈形排列问题

9.7图的计数多项式

9.8P61ya定理的推广

9.9Pdlya定理的应用

第10章线性不定方程

10.1母函数解法

10.2引入辅助参数

10.3一个新方法

10.4Na.b（n）的进一步讨论

第11章组合恒等式

11.1几个基本的变形与等式

11.2组合恒等式的证明Ⅰ

11.3组合恒等式的证明Ⅱ

11.4组合恒等式的证明Ⅲ

11.5组合恒等式的证明Ⅳ

11.6证明恒等式的WZ方法

第12章图标号问题

12.1引言

12.2优美标号族

12.3协调标号族

12.4幻型标号族

12.5其他的标号类型

第13章其他组合问题

13.1幻方与数阵

13.2覆盖与铺砌

13.3组合游戏

参考文献

附录组合学有关名词术语

　　本书共13章，分为三部分，第一部分包括13章，全面概述了经典的组合计数方法，并介绍了组合计数的两个主要工具递归关系和母函数；第二部分包括49章，以较大的篇幅详细介绍了几类重要的组合数以及容斥原理、整数分拆、Hall定理、Ramsey理论和Polya理论；第三部分包括1013章，对线性不定方程、组合恒等式、图标号、幻方以及铺砌、覆盖与剖分等分别进行了较充分的讨论，附录中列出了组合学的有关名词符号。　　本书系统阐述组合学的经典理论和方法，详细介绍了递归关系、母函数、容斥原理等计数工具以及整数分拆、Hall定理和Ramsey理论，着重介绍了几类重要的组合数和P61ya理论，并对线性不定方程、组合恒等式、图标号、幻方以及铺砌、覆盖与剖分等给出了相当的论述。全书深入浅出、条理清晰、结论严谨，具有一定的广度和深度，并选用了适量的趣味问题和应用实例，列出了一些前沿性结论和有待探讨的问题。　　本书可作为数学与应用数学专业的高年级本科生、研究生及教师的教材或教学参考书，也可供相关专业的科研人员或广大数学爱好者阅读参考。