组合数学(原书第5版)
使用本教材的高校
本书侧重于组合数学的概念和思想，包括鸽巢原理、计数技术、排列组合、Polya计数法、二项式系数、容斥原理、生成函数和递推关系以及组合结构（匹配、实验设计、图）等，深入浅出地表达了作者对该领域全面和深刻的理解。
基本信息
- 原书名：Introductory Combinatorics，Fifth Edition
- 原出版社： Prentice Hall
- 作者： (美)Richard A.Brualdi
- 译者： 冯速
- 丛书名： 计算机科学丛书
- 出版社：机械工业出版社
- ISBN：9787111377870
- 上架时间：2012-5-9
- 出版日期：2012 年5月
- 开本：16开
- 页码：371
- 版次：5-1
- 所属分类：计算机 > 计算机科学理论与基础知识 > 数值计算 > 综合
教材
【插图】
编辑推荐
系统阐述组合数学基础、理论、方法和实例的优秀教材，出版30多年来多次改版，被mit、哥伦比亚大学、uiuc、威斯康星大学等众多国外高校采用，对国内外组合数学教学产生了较大影响，也是相关学科的主要参考文献之一。
内容简介
作译者
Richard A. Brualdi 美国威斯康星大学麦迪逊分校数学系教授（现已退休），曾任系主任多年。他的研究方向包括组合数学、图论、线性代数和矩阵理论、编码理论等。Brualdi教授的学术活动非常丰富，担任过多种学术期刊的主编。2000年由于在组合数学研究中所做出的杰出终身成就而获得组合数学及其应用学会颁发的欧拉奖章。
目录
《组合数学(原书第5版)》
出版者的话
译者序
前言
第1章 什么是组合数学1
1.1 例子：棋盘的完美覆盖2
1.2 例子：幻方4
1.3 例子：四色问题6
1.4 例子：36军官问题7
1.5 例子：最短路径问题9
1.6 例子：相互重叠的圆10
1.7 例子：Nim游戏10
1.8 练习题12
第2章 排列与组合16
2.1 四个基本的计数原理16
2.2 集合的排列21
2.3 集合的组合(子集)24
2.4 多重集合的排列28
2.5 多重集合的组合32
2.6 有限概率34
出版者的话
译者序
前言
第1章 什么是组合数学1
1.1 例子：棋盘的完美覆盖2
1.2 例子：幻方4
1.3 例子：四色问题6
1.4 例子：36军官问题7
1.5 例子：最短路径问题9
1.6 例子：相互重叠的圆10
1.7 例子：Nim游戏10
1.8 练习题12
第2章 排列与组合16
2.1 四个基本的计数原理16
2.2 集合的排列21
2.3 集合的组合(子集)24
2.4 多重集合的排列28
2.5 多重集合的组合32
2.6 有限概率34
译者序
组合数学是计算机出现以后迅速发展起来的一门数学分支。计算机科学即算法的科学，而计算机所处理的对象是离散的数据，所以离散对象的处理就成了计算机科学的核心，而研究离散对象的科学恰恰就是组合数学。
本书译自Richard A.Brualdi的《Introductory Combinatorics，Fifth Edition》一书，着重于组合学思想的阐述，包括对鸽巢原理、计数技术、排列与组合、Pólya计数法、二项式系数、容斥原理、生成函数与递推关系以及一些组合结构（如匹配、设计和图等）的讨论。第5版经过较大的修订，添加了有限概率、相异代表系、匹配数等内容，同时删除若干不影响对组合数学理解的内容，或将其移作练习题，以保持本书内容不致过于庞大而使读者却步。为方便读者阅读、理解，作者在这一版中做出了很多努力。比如，使用“子集”来描述“组合”的概念，这两个术语虽然本质上是等价的，但对于初学者来说，显然“子集”要比“组合”容易理解得多。更重要的是，通过布局上的调整，使前后文更加通顺，衔接更加自然。
在本书前言中，作者比较详细地介绍了各章的内容和它们之间的关系，谈到了使用本书伸缩性的授课方案以及作者讲授时的经验和偏好，这对于我们深入了解本书的内容和结构以便将它作为教材恰当地使用是很有帮助的。本书原著通俗流畅，深入浅出，生动灵活的写作风格反映了作者对该领域的热情和作为课程讲授的乐趣。
本书第5版的翻译工作参考了第4版译稿，感谢第4版译者的辛勤工作。在翻译过程中，译者对原书中出现的明显排印错误进行了修改，并对基本流算法的陈述做了改写，以便更容易理解，希望不是画蛇添足。
除封面署名外，参与本书翻译工作的人员还有马晶、易超、龚治、李思源、陈辉、周亦洋、韦添等。
由于时间和水平的限制，译文中难免疏漏和错误，期盼广大读者的批评与指正。
译者
2012年2月
本书译自Richard A.Brualdi的《Introductory Combinatorics，Fifth Edition》一书，着重于组合学思想的阐述，包括对鸽巢原理、计数技术、排列与组合、Pólya计数法、二项式系数、容斥原理、生成函数与递推关系以及一些组合结构（如匹配、设计和图等）的讨论。第5版经过较大的修订，添加了有限概率、相异代表系、匹配数等内容，同时删除若干不影响对组合数学理解的内容，或将其移作练习题，以保持本书内容不致过于庞大而使读者却步。为方便读者阅读、理解，作者在这一版中做出了很多努力。比如，使用“子集”来描述“组合”的概念，这两个术语虽然本质上是等价的，但对于初学者来说，显然“子集”要比“组合”容易理解得多。更重要的是，通过布局上的调整，使前后文更加通顺，衔接更加自然。
在本书前言中，作者比较详细地介绍了各章的内容和它们之间的关系，谈到了使用本书伸缩性的授课方案以及作者讲授时的经验和偏好，这对于我们深入了解本书的内容和结构以便将它作为教材恰当地使用是很有帮助的。本书原著通俗流畅，深入浅出，生动灵活的写作风格反映了作者对该领域的热情和作为课程讲授的乐趣。
本书第5版的翻译工作参考了第4版译稿，感谢第4版译者的辛勤工作。在翻译过程中，译者对原书中出现的明显排印错误进行了修改，并对基本流算法的陈述做了改写，以便更容易理解，希望不是画蛇添足。
除封面署名外，参与本书翻译工作的人员还有马晶、易超、龚治、李思源、陈辉、周亦洋、韦添等。
由于时间和水平的限制，译文中难免疏漏和错误，期盼广大读者的批评与指正。
译者
2012年2月
前言
在这一新版本中，我做了一些细微的改变，具体概括如下：
在第1章，新增加了一节（1.6节），讨论相互重叠圆的问题，用来具体说明后面章节中所讨论的某些计数问题。之前，这一节的相关内容出现在第7章。
第1章中原来关于切割立方体的一节已经删除，但是相关内容放在练习题中。
之前版本中的第2章（鸽巢原理）改成了第3章。之前版本中关于排列和组合的第3章改成了第2章。帕斯卡公式在之前的版本中第一次出现在第5章中，现在出现在第2章中。另外，为了清晰起见，在关于集合的论述中我们不再强调“组合”这一术语，而启用了一个本质上等价的术语“子集”。然而，在多重集合的情况下，我们继续使用“组合”，而不使用在我们看来易产生混淆的术语“多重子集”。
此版本的第2章包含一节（2.6节）有限概率简介。
此版本的第3章包含Ramsey定理的证明。
第7章的变化比较大，其中生成函数和指数生成函数移到了本章靠前部分（7.2节和7.3节），成为更核心的内容。
分拆数这一节（8.3节）做了扩展。
之前版本中关于二分图匹配的第9章做了根本的改变。现在的第9章是新插入的章节，讨论的是相异代表系（SDR）的问题，包括婚姻和稳定婚姻匹配问题，而不再讨论二分图。
第9章这样改动的结果是，介绍图论的章节（第11章）不再假设先前已介绍过二分图的知识。
再论图论一章（之前版本中的第13章）现在变成了第12章。在本章中，新增加了关于图的匹配数一节（12.5节），在这一节中，第9章中SDR的基础结果被用于二分图。
有向图和网络这一章（之前是第12章）现在是第13章。它新增加了一节，回顾了二分图的匹配，其中有些相关内容出现在之前版本的第9章中。
对于第5版，除了以上列出的这些变化之外，还更正了我注意到的所有印刷错误；增加了少量的说明；改动了一些顺序，使前后文更加通顺；另外还增加了练习题，第5版中共有700道练习题。
根据多年来很多读者的评论，这本书似乎已经通过了时间的检验。因此，我总是犹豫不决而迟迟没有做出更多的改变，也没有增加更多的新话题。我不希望一本书“太长”（这一前言也不会太长），也不愿意让这本书迎合每个人的癖好。不过，我的确做了上述细节上的改变，相信这些改变会使这本书更加完善。
与之前各版本一样，这一版可以用于一到两个学期的本科生课程。第一个学期可以侧重计数，而第二个学期可以侧重图论和设计。也可以把相关内容合并在一起作为一个学期的课程，如讲解一些计数和图论知识，或者一些计数与设计理论知识，或者选择其他的组合搭配。下面简要说明各章以及它们之间的相互关系。
第1章是介绍，我通常只从中选出一两个话题，最多花两节课时间。第2章讨论的是排列和组合，这一章应该全讲。第3章讨论的是鸽巢原理，这一章至少应该做简单介绍。但是，需要注意的是，后面没有用到一些较难的鸽巢原理应用以及关于Ramsey定理那一节的内容。第4章到第8章主要讨论计数技巧及计数序列的相关性质。这些内容应该按照顺序依次讲解。第4章讨论的是排列和组合的生成方案，包括4.5节的偏序和等价关系的介绍。我认为至少应该讲解等价关系，因为它们在数学中无处不在。除了第5章关于偏序集这一节（5.7节）之外，其余各章本质上都独立于第4章，所以这一章可以跳过或者略讲。你也可以选择根本不讲解偏序集。我把关于偏序集的内容分成两节（4.5节和5.7节），目的是给学生少许时间去消化某些概念。第5章讨论的是二项式系数的性质，而第6章所涉及的是容斥原理。莫比乌斯反演那节（6.6节）可以归结到容斥原理，这一节对后面没有用。第7章比较长，讨论的是生成函数和递推关系求解。第8章主要讨论的是Catalan数、第一和第二类Stirling数、分拆数以及大Schrder数和小Schrder数。对于这一章的各节你可以选择学习，也可以选择跳过。第8章之后的各章与它都没有关系。第9章讨论的是相异代表系（所谓的婚姻问题）。第12章和第13章要用到第9章的一些内容以及第10章中的拉丁方一节（10.4节）。第10章讨论的是组合设计的某些内容，它与本书其后的内容无关。第11章和第12章对图论进行了比较全面的讨论，并稍侧重于某些图论算法。第13章讨论的是有向图和网络流。第14章讨论置换群作用下的计数问题，这一章大量使用了前面的计数思想。除了最后一个例子之外，它与关于图论和设计的各章无关。
当我将本书用于一学期课程时，喜欢以第14章的Burnside定理及其几个应用收尾。这种做法使学生们能够解决很多计数问题，而这些用前面几章的计数技巧是不能解决的。通常，我不会讲Pólya定理。
继第14章之后，我给出了本书一些练习题的答案和提示。少数练习题旁边标上了“”号，表明它们有相当的挑战性。每一个证明结束及每一个例子结束处都标有“□”号予以明示。
很难评说学习这本书所需要的前提条件。与其他教科书一样，高度激发学生的热情、提起学生的兴趣是很有用的，另外还需要指导教师的热情投入。也许这些前提条件应该这样描述为好：有完备的数学知识，即成功地学习了数学分析相关内容以及线性代数的初等课程。本书对数学分析使用极少，而涉及线性代数的内容也不多，因此，对不熟悉这些内容的读者来说，阅读本书应该不会产生任何问题。
令我感到最欣慰的就是自从本书第1版出版之后三十多年来，它仍然得到数学界专业人士的认可。
在第1章，新增加了一节（1.6节），讨论相互重叠圆的问题，用来具体说明后面章节中所讨论的某些计数问题。之前，这一节的相关内容出现在第7章。
第1章中原来关于切割立方体的一节已经删除，但是相关内容放在练习题中。
之前版本中的第2章（鸽巢原理）改成了第3章。之前版本中关于排列和组合的第3章改成了第2章。帕斯卡公式在之前的版本中第一次出现在第5章中，现在出现在第2章中。另外，为了清晰起见，在关于集合的论述中我们不再强调“组合”这一术语，而启用了一个本质上等价的术语“子集”。然而，在多重集合的情况下，我们继续使用“组合”，而不使用在我们看来易产生混淆的术语“多重子集”。
此版本的第2章包含一节（2.6节）有限概率简介。
此版本的第3章包含Ramsey定理的证明。
第7章的变化比较大，其中生成函数和指数生成函数移到了本章靠前部分（7.2节和7.3节），成为更核心的内容。
分拆数这一节（8.3节）做了扩展。
之前版本中关于二分图匹配的第9章做了根本的改变。现在的第9章是新插入的章节，讨论的是相异代表系（SDR）的问题，包括婚姻和稳定婚姻匹配问题，而不再讨论二分图。
第9章这样改动的结果是，介绍图论的章节（第11章）不再假设先前已介绍过二分图的知识。
再论图论一章（之前版本中的第13章）现在变成了第12章。在本章中，新增加了关于图的匹配数一节（12.5节），在这一节中，第9章中SDR的基础结果被用于二分图。
有向图和网络这一章（之前是第12章）现在是第13章。它新增加了一节，回顾了二分图的匹配，其中有些相关内容出现在之前版本的第9章中。
对于第5版，除了以上列出的这些变化之外，还更正了我注意到的所有印刷错误；增加了少量的说明；改动了一些顺序，使前后文更加通顺；另外还增加了练习题，第5版中共有700道练习题。
根据多年来很多读者的评论，这本书似乎已经通过了时间的检验。因此，我总是犹豫不决而迟迟没有做出更多的改变，也没有增加更多的新话题。我不希望一本书“太长”（这一前言也不会太长），也不愿意让这本书迎合每个人的癖好。不过，我的确做了上述细节上的改变，相信这些改变会使这本书更加完善。
与之前各版本一样，这一版可以用于一到两个学期的本科生课程。第一个学期可以侧重计数，而第二个学期可以侧重图论和设计。也可以把相关内容合并在一起作为一个学期的课程，如讲解一些计数和图论知识，或者一些计数与设计理论知识，或者选择其他的组合搭配。下面简要说明各章以及它们之间的相互关系。
第1章是介绍，我通常只从中选出一两个话题，最多花两节课时间。第2章讨论的是排列和组合，这一章应该全讲。第3章讨论的是鸽巢原理，这一章至少应该做简单介绍。但是，需要注意的是，后面没有用到一些较难的鸽巢原理应用以及关于Ramsey定理那一节的内容。第4章到第8章主要讨论计数技巧及计数序列的相关性质。这些内容应该按照顺序依次讲解。第4章讨论的是排列和组合的生成方案，包括4.5节的偏序和等价关系的介绍。我认为至少应该讲解等价关系，因为它们在数学中无处不在。除了第5章关于偏序集这一节（5.7节）之外，其余各章本质上都独立于第4章，所以这一章可以跳过或者略讲。你也可以选择根本不讲解偏序集。我把关于偏序集的内容分成两节（4.5节和5.7节），目的是给学生少许时间去消化某些概念。第5章讨论的是二项式系数的性质，而第6章所涉及的是容斥原理。莫比乌斯反演那节（6.6节）可以归结到容斥原理，这一节对后面没有用。第7章比较长，讨论的是生成函数和递推关系求解。第8章主要讨论的是Catalan数、第一和第二类Stirling数、分拆数以及大Schrder数和小Schrder数。对于这一章的各节你可以选择学习，也可以选择跳过。第8章之后的各章与它都没有关系。第9章讨论的是相异代表系（所谓的婚姻问题）。第12章和第13章要用到第9章的一些内容以及第10章中的拉丁方一节（10.4节）。第10章讨论的是组合设计的某些内容，它与本书其后的内容无关。第11章和第12章对图论进行了比较全面的讨论，并稍侧重于某些图论算法。第13章讨论的是有向图和网络流。第14章讨论置换群作用下的计数问题，这一章大量使用了前面的计数思想。除了最后一个例子之外，它与关于图论和设计的各章无关。
当我将本书用于一学期课程时，喜欢以第14章的Burnside定理及其几个应用收尾。这种做法使学生们能够解决很多计数问题，而这些用前面几章的计数技巧是不能解决的。通常，我不会讲Pólya定理。
继第14章之后，我给出了本书一些练习题的答案和提示。少数练习题旁边标上了“”号，表明它们有相当的挑战性。每一个证明结束及每一个例子结束处都标有“□”号予以明示。
很难评说学习这本书所需要的前提条件。与其他教科书一样，高度激发学生的热情、提起学生的兴趣是很有用的，另外还需要指导教师的热情投入。也许这些前提条件应该这样描述为好：有完备的数学知识，即成功地学习了数学分析相关内容以及线性代数的初等课程。本书对数学分析使用极少，而涉及线性代数的内容也不多，因此，对不熟悉这些内容的读者来说，阅读本书应该不会产生任何问题。
令我感到最欣慰的就是自从本书第1版出版之后三十多年来，它仍然得到数学界专业人士的认可。
媒体评论
本书是系统阐述组合数学基础、理论、方法和实例的优秀教材，出版30多年来多次改版，被MIT、哥伦比亚大学、UIUC、威斯康星大学等众多国外高校采用，对国内外组合数学教学产生了较大影响，也是相关学科的主要参考文献之一。
本书侧重于组合数学的概念和思想，包括鸽巢原理、计数技术、排列组合、Polya计数法、二项式系数、容斥原理、生成函数和递推关系以及组合结构（匹配、实验设计、图）等，深入浅出地表达了作者对该领域全面和深刻的理解。除包含第4版中的内容外，本版又进行了更新，增加了有限概率、匹配数等内容。此外，各章均包含大量练习题，并在书末给出了参考答案与提示。
本书侧重于组合数学的概念和思想，包括鸽巢原理、计数技术、排列组合、Polya计数法、二项式系数、容斥原理、生成函数和递推关系以及组合结构（匹配、实验设计、图）等，深入浅出地表达了作者对该领域全面和深刻的理解。除包含第4版中的内容外，本版又进行了更新，增加了有限概率、匹配数等内容。此外，各章均包含大量练习题，并在书末给出了参考答案与提示。
书摘
插图：
在生活中组合数学随处可见。你是否曾经遇到这样的问题：有n个参赛队，每个队只能与其他队比赛一次，那么有多少场比赛呢？你是否曾经想过，在用笔遍历某个网络时，在笔不离开纸且网络任何一部分只能经过一次的条件下，有多少遍历方法呢？你是否计算过纸牌游戏中的满堂红的手数，以便确定满堂红的概率是多少呢？你是否尝试着解决一个数独问题呢？这些都是组合问题。正如这些例子所揭示的那样，组合数学扎根于数学和游戏之中。过去研究过的许多问题，不论是出于娱乐还是出于美学上的需求，现今在纯科学和应用科学领域都有着高度的重要性。今天，组合数学是数学的一个重要分支，组合数学高速成长起来的原因之一是计算机在我们的社会中起着重要的作用。因为计算机的速度不断增加，所以它们已经能够处理大型问题，这在之前是不可能做到的。但是计算机不能独立运行，它们必须按程序运行。这些程序的基础通常是用来求解这些问题的组合数学算法。这些程序的有效性分析主要从程序的运行时间和存储需求等方面考虑，这其中涉及更多的组合数学思想。
组合数学持续发展的另一个原因就是它能够运用到很多学科，而之前这些学科与数学几乎没有关联。因此，我们会发现组合数学的思想和技术不仅用于传统的应用科学领域（比如说物理学），还应用于社会科学、生物科学、信息论等领域。另外，组合数学和组合数学思想在很多数学分支中也变得越来越重要。
组合数学所关心的问题就是把某个集合中的对象排列成某种模式，使其满足一些指定的规则。下面是两种反复出现的通用问题：
·排列的存在性。当我们想排列一个集合的对象使其满足特定条件时，这样的排列是否存在也许不是显然的。这是最基本的问题。如果这样的排列不总是可行的，那么我们很自然就要问，在什么样的条件（必要条件和充分条件）下可以实现所希望的排列。
·排列的列举或分类。当指定的排列可行时，就有可能存在很多种实现它的方法。于是我们就要计数或分类不同类型的排列。
如果特定问题的排列数量较小，那么我们就可以列出这些排列。这里，重要的是要理解列出所有排列和确定它们的数量之间的差异。一旦这些排列被列出来，那么我们就可以对某个自然数n建立它们与整数集合{1，2，…，n}之间的一一对应，从而计数这些排列。我们的计算方法就是：1，2，3，…。然而，我们主要关心的是，对于特定类型的排列，在不列出它们的情况下确定这些排列数的技术问题。当然，这个排列数目也许非常大，以至于我们无法把它们全部列出来。
下面是另外两种常常出现的组合问题。
·研究已知的排列。在你完成了构建满足特定条件的排列之后（也许这是一项困难的工作），接下来可以研究它的性质和结构。
·构造最优排列。如果存在多个可行的排列，那么我们也许想要确定满足某些优化标准的排列，也就是说，在某种指定的意义下去寻找一个“最好”或者“最优”的排列。
因此，关于组合数学的一般描述也许就是，组合数学是研究离散构造的存在、计数、分析和优化等问题的一门学科。虽然一些离散结构是无限的，但是在本书中，离散一般指的是有限。 组合数学验证发现的主要工具之一是数学归纳法。归纳法是一个强大的方法，在组合数学中尤为如此。通常情况下，用数学归纳法证明一个较强的结果要比证明一个较弱的结果更为容易。虽然归纳步骤需要证明更多的东西，但归纳假设可以更强。数学归纳法的技巧是寻找假设和结论的正确平衡以便进行归纳。我们假定读者熟悉归纳法，通读了这本书之后，读者会对此有更加深刻的了解。
组合问题的解决方案通常可以使用专门论证来获取，有时需要结合一般理论的使用。我们不可能总是退回到公式或者已知的结果上。组合问题的一个典型的解决方法可能包含下面几个步骤：（1）建立数学模型；（2）研究模型；（3）计算若干小案例，树立信心，洞察一切；（4）运用详细的推理和巧思最终找到问题的答案。计数问题、容斥原理、鸽巢原理、递推关系和生成函数、Burnside定理和Polya计数公式等都是一般原理和方法的案例，我们将在后面各章陆续讲解它们。然而，有时候还需要你的聪明才智，能够看破要使用的专门方法或者公式并知道如何去运用它们。因此，在解决组合问题中经验是非常重要的。也就是说，一般来说用组合数学解决问题与用数学解决问题一样，你解决的问题越多，你就越有可能解决随后的新问题。
下面我们考虑几个组合问题的粗浅例子。前面几个问题相对简单，而后面几个问题的结果曾经是组合数学的主要成就。我们将在后续章节中更加详细地讨论其中的几个问题。
在生活中组合数学随处可见。你是否曾经遇到这样的问题：有n个参赛队，每个队只能与其他队比赛一次，那么有多少场比赛呢？你是否曾经想过，在用笔遍历某个网络时，在笔不离开纸且网络任何一部分只能经过一次的条件下，有多少遍历方法呢？你是否计算过纸牌游戏中的满堂红的手数，以便确定满堂红的概率是多少呢？你是否尝试着解决一个数独问题呢？这些都是组合问题。正如这些例子所揭示的那样，组合数学扎根于数学和游戏之中。过去研究过的许多问题，不论是出于娱乐还是出于美学上的需求，现今在纯科学和应用科学领域都有着高度的重要性。今天，组合数学是数学的一个重要分支，组合数学高速成长起来的原因之一是计算机在我们的社会中起着重要的作用。因为计算机的速度不断增加，所以它们已经能够处理大型问题，这在之前是不可能做到的。但是计算机不能独立运行，它们必须按程序运行。这些程序的基础通常是用来求解这些问题的组合数学算法。这些程序的有效性分析主要从程序的运行时间和存储需求等方面考虑，这其中涉及更多的组合数学思想。
组合数学持续发展的另一个原因就是它能够运用到很多学科，而之前这些学科与数学几乎没有关联。因此，我们会发现组合数学的思想和技术不仅用于传统的应用科学领域（比如说物理学），还应用于社会科学、生物科学、信息论等领域。另外，组合数学和组合数学思想在很多数学分支中也变得越来越重要。
组合数学所关心的问题就是把某个集合中的对象排列成某种模式，使其满足一些指定的规则。下面是两种反复出现的通用问题：
·排列的存在性。当我们想排列一个集合的对象使其满足特定条件时，这样的排列是否存在也许不是显然的。这是最基本的问题。如果这样的排列不总是可行的，那么我们很自然就要问，在什么样的条件（必要条件和充分条件）下可以实现所希望的排列。
·排列的列举或分类。当指定的排列可行时，就有可能存在很多种实现它的方法。于是我们就要计数或分类不同类型的排列。
如果特定问题的排列数量较小，那么我们就可以列出这些排列。这里，重要的是要理解列出所有排列和确定它们的数量之间的差异。一旦这些排列被列出来，那么我们就可以对某个自然数n建立它们与整数集合{1，2，…，n}之间的一一对应，从而计数这些排列。我们的计算方法就是：1，2，3，…。然而，我们主要关心的是，对于特定类型的排列，在不列出它们的情况下确定这些排列数的技术问题。当然，这个排列数目也许非常大，以至于我们无法把它们全部列出来。
下面是另外两种常常出现的组合问题。
·研究已知的排列。在你完成了构建满足特定条件的排列之后（也许这是一项困难的工作），接下来可以研究它的性质和结构。
·构造最优排列。如果存在多个可行的排列，那么我们也许想要确定满足某些优化标准的排列，也就是说，在某种指定的意义下去寻找一个“最好”或者“最优”的排列。
因此，关于组合数学的一般描述也许就是，组合数学是研究离散构造的存在、计数、分析和优化等问题的一门学科。虽然一些离散结构是无限的，但是在本书中，离散一般指的是有限。 组合数学验证发现的主要工具之一是数学归纳法。归纳法是一个强大的方法，在组合数学中尤为如此。通常情况下，用数学归纳法证明一个较强的结果要比证明一个较弱的结果更为容易。虽然归纳步骤需要证明更多的东西，但归纳假设可以更强。数学归纳法的技巧是寻找假设和结论的正确平衡以便进行归纳。我们假定读者熟悉归纳法，通读了这本书之后，读者会对此有更加深刻的了解。
组合问题的解决方案通常可以使用专门论证来获取，有时需要结合一般理论的使用。我们不可能总是退回到公式或者已知的结果上。组合问题的一个典型的解决方法可能包含下面几个步骤：（1）建立数学模型；（2）研究模型；（3）计算若干小案例，树立信心，洞察一切；（4）运用详细的推理和巧思最终找到问题的答案。计数问题、容斥原理、鸽巢原理、递推关系和生成函数、Burnside定理和Polya计数公式等都是一般原理和方法的案例，我们将在后面各章陆续讲解它们。然而，有时候还需要你的聪明才智，能够看破要使用的专门方法或者公式并知道如何去运用它们。因此，在解决组合问题中经验是非常重要的。也就是说，一般来说用组合数学解决问题与用数学解决问题一样，你解决的问题越多，你就越有可能解决随后的新问题。
下面我们考虑几个组合问题的粗浅例子。前面几个问题相对简单，而后面几个问题的结果曾经是组合数学的主要成就。我们将在后续章节中更加详细地讨论其中的几个问题。
