组合数学的基本原理是在17世纪到18世纪由Leibniz、Jacob和Euler等数学家建立起来的。早期组合数学的研究来源于概率论中的相关问题。进入20世纪后，组合理论与数学其他分支的联系越来越密切，众多学者将组合学与数学其他分支的有关理论相结合，得到了许多富有意义的结果：1928年，英国数学家Ramsey提出并证明了一个关于集合论的Ramsey定理；1935年Whitney同时推广了图和矩阵的概念，引入了拟阵；1937年，P?lya将群的理论引入组合数学中，给出了一种普遍适用的计数方法--P?lya定理；1964年，Rota把数论中的麦比乌斯函数及反演公式应用于定义在一般偏序集上的二元函数构成的"结合函数"之上，引进了广义麦比乌斯函数及反演公式。如今，组合数学已成为数学中发展最为迅速的分支之一。

本书内容简介  本书的目的是尽可能详细地介绍组合数学中必不可少的核心理论，而对于基础组合学中的许多结论（尤其是与程序设计竞赛关系很小的内容）则被省略了。希望通过这样的处理，使参加程序设计竞赛的读者能够从这些核心理论的学习中掌握组合数学研究问题的方法，而不是单纯地了解理论。

大多数组合数学的书籍将重点放在定理的证明上，而本书则用大量的篇幅介绍如何用组合数学的原理来设计算法，并通过各种方法来不断地优化算法，使其具有较低的时间复杂度和较小的空间开销，同时对于一般的组合数学教材中很少涉及的拟阵理论也给予了介绍。除此之外，还用一定的篇幅介绍与理论计算机科学密切相关的NP-问题，SAT问题等内容。对于部分例题，本书给出了多种求解算法，并对程序在具体运行时所需要的时间加以比较。

本书阅读指南  全书共分八章。

第1章介绍与算法有关的基本理论。内容涉及：在复杂度分析中使用的基本记号。时间复杂度与空间复杂度的概念、平摊分析、P类与NP类、规约、NP-完全问题等。

第2章介绍组合数学的研究范围。除了给出组合数学研究的若干经典问题外，还介绍鸽笼原理的知识。

第3章介绍排列与组合的有关理论，以及排列与组合的生成算法。

第4章介绍容斥原理，并涉及错位排列和欧拉函数的知识。

第5章是母函数。这一章从二项式定理引入普通型母函数，并引入指数型母函数，在5.3~5.5节中介绍三个程序设计竞赛中的题目。5.6节总结组合计数的常见方法，5.7节通过介绍NPC问题的母函数表示，向读者展示了母函数理论更为广泛的应用。

第6章介绍拟阵的有关理论。6.1节引入了拟阵的定义；6.2节着重介绍与算法设计相关的拟阵的性质；6.3节使用拟阵的方法，分析了若干图的贪心算法。

第7章作为拟阵理论的推广，对贪心算法给予了介绍。7.1节介绍贪心算法的定义与特点；7.2节分析一道程序设计竞赛试题；7.3节讨论用贪心算法求近似解的有关问题。

第8章介绍Pólya定理。8.1节介绍关于群和置换群的简单知识；8.2节和8.3节分别介绍Burnside引理和Pólya定理。

附录中介绍了本书所使用的若干基本记号和与本书内容密切相关的其他数学知识，供没有系统学习过离散数学、数论与级数的读者参考。建议首先阅读此附录，可提高学习效率。

本书用若干个完整的章节来介绍近几年来在国际和国内各类程序设计竞赛中运用组合数学方法求解的典型题目，而那些在程序设计竞赛中涉及较少的关于组合数学中的有关结论，则放到了相关章节的例题中，这使得读者可以用尽可能少的时间来掌握组合学中的基本原理。书中介绍的有关内容的扩展放到了习题中，给读者留下了思考的余地。

本书习题的说明

本书的习题分为四类：

1．组合数学基础知识的训练

这一类题目主要是帮助读者巩固在本书相应章节所介绍的基础知识。这类问题在题号后标以[B]。在本书的学习过程中，建议读者独立地完成这一类习题。

2．更难一些的题目和组合数学相关知识的扩展

这一类问题主要是与书中所介绍的理论相关内容的扩展以及更难一些的题目。由于本书并不是一本介绍组合数学理论的基础教材，所以在组合数学中与程序设计竞赛关系不大但却能很好地体现组合数学研究方法的相关问题和组合数学中的一些重要结论，在这类习题中给予了介绍。这类问题在题目的序号后标以[F]。

3．算法的优化与分析

本书中部分习题要求读者改进例题中的有关算法，或者是分析算法的时间复杂度和空间复杂度。这类问题在题号后标以[D]。

4．程序设计竞赛试题

这部分题目选自世界各地的大中学生程序设计竞赛。这类问题在题号后标以[P]，并且位于每章习题的后半部分。

第1章介绍在本书后续章节的学习中需要用到的算法知识。所以在这一章的习题中基础性的题目标以[B]，比较难的题目标以[F]。

书中个别的习题前会有两个英文字母。一个标有[PD]的习题既要求读者根据题目的意图编写程序，同时要求做出与题目有关的算法分析。这类题目是一些很典型的问题，读者应格外引起注意。作者着重推荐的题目在题号前加以4标记。

本书致谢

本书是在清华大学计算机科学与技术系博士生导师、国际信息学奥林匹克中国队总教练吴文虎教授的指导下完成的，他不仅仔细地审阅了本书的初稿，而且提出了许多宝贵的修改意见。复旦大学ACM竞赛组吴永辉老师与作者就书稿的内容进行了多次讨论。清华大学出版社的编辑在本书的出版过程中做了大量工作，使得本书更加完善。在此表示衷心的感谢。

由于作者水平有限，书中难免有疏漏和错误之处，恳请广大读者批评指正。

作者电子邮件地址：sunhe@fudan.edu.cn

                                  孙   贺

2005年4月于上海