译者序

离散数学是大学计算机科学与技术专业最重要的必修课程之一，是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。由于计算机是一个离散结构，它只能处理离散的或者离散化了的数量关系，因此，无论是计算机科学本身，还是与计算机科学及其应用密切相关的现代科学研究领域，都面临着如何为离散结果建立相应数学模型的问题；又如何将已用连续数量关系建立起来的数学模型进行离散化的问题，从而可由计算机加以处理。因此，随着计算机科学的发展，离散数学作为计算机科学的一种数学工具，其作用显得更加重要。同时，离散数学也是许多计算机科学与技术专业课程的基础：其基本概念、基本理论和基本方法大量地应用在数据结构、操作系统、人工智能、计算机网络、编译原理、算法设计与分析等课程中。

组合数学是随着计算机科学的蓬勃发展而完善起来的，并且已经成为一门极富生命力的数学分支。许多理论学科和应用学科向组合数学提出了大量的具有理论和实际意义的课题，促使它产生许多新理论，如区组设计、组合优化、组合算法等。同时，组合数学也是研究图论、密码学、编码理论、算法复杂性的基本数学工具。

国内外所有高校的计算机科学与技术专业都开设了针对本科的离散数学与组合数学课程。R. P. Grimaldi教授具有极其丰富的教学理论和实践经验，他的这本《离散数学与组合数学》（Discrete and Combinatorial Mathematics）一书选材广泛，叙述深入浅出，推理严谨，习题丰富，其英文版现已出到第5版，为美国、澳大利亚、加拿大、英格兰、新加坡、南非、瑞典等国家的众多大学采用。我们非常高兴能将这本优秀教材引荐给中国的广大读者。

本书与国内出版的离散数学与组合数学教材相比有如下特点：

 有利于学生自学。3个附录针对离散数学与组合数学有关的数学基础知识做了适当的铺垫和介绍。全书行文严谨，语言生动，将基本概念、基本定理讲解的非常透彻。

 叙述风格和选材非常适合教学。首先本书的内容由浅入深，由具体到抽象。其次教师可以根据不同的教学要求选择适当的模块加以组合。

 内容极其丰富。包括计数、数理逻辑、集合论、图论、应用代数等基本内容，有许多带有详细解释的例子、定义、定理及证明。

 选配了大量难度适当的习题，并给出了奇数编号习题的参考答案或提示。

 与计算机技术密切相关。包括许多算法的描述、时间复杂性的分析、设计算法以及上机实现的要求。

本书是一本优秀的离散数学与组合数学的入门书籍，适合作为计算机科学与技术专业的离散数学与组合数学教材。本书的翻译主要由林永钢完成，刘庆晖、刘云蓉、林茂春参与翻译了组合数学方面的部分内容，最后由林永钢对全书进行了统稿和审阅。译者本着尊重原著的原则，努力在翻译的准确性与灵活性之间取得平衡，同时也更正了原著中的少量错误。由于译者水平有限，译文的不妥之处在所难免，恳请读者批评指正。         

林永钢2007年4月于北京理工大学

序言

自从1982年9月2日我签署合同来写作目前这本教材的第1版时，到现在已经有20多年了。那时我根本没有想过还会出以后的版本。因此，在这本教材被许多教师特别是众多学生所接受时，我既感到荣幸又十分欣喜。在美国，许多大学和学院都采用了此书的前四版。同时采用的还有其他国家和地区，比如澳大利亚、加拿大、英格兰、爱尔兰、日本、墨西哥、荷兰、苏格兰、新加坡、南非以及瑞典。在这里，我希望第5版可以继续启发和激励那些想要对被称为离散数学的迷人数学领域有所研究的读者。

过去40年中的技术进步使得大学课程有了很大变化。这些变化也导致了许多单学期课程以及多学期课程的发展，其中引入了以下的一些内容：

1. 离散方法，它强调了存在于许多问题和结构中的内在有限性；

2. 组合数学——计数代数，以及与大量有限结构令人着迷的相互联系；

3. 图论及其应用，以及与诸如数据结构和最优化方法等其他领域的相互关系；

4. 有限代数结构，它出现在许多学科中，比如编码理论、计数方法、门网络、组合设计。

研究这四个主题中的所有或者部分内容的主要原因是：人们发现在计算机科学的研究过程中它们有着广泛的应用——特别是在数据结构、计算机语言理论以及算法分析领域中。此外，它们在工程学、生命科学、统计学以及社会科学中也应用广泛。因此，离散数学与组合数学的学科性质就注定它们要为许多专业的学生提供有价值的内容——不仅仅是数学专业或者计算机科学专业。

这本新版教材的主要意图是继续对离散数学与组合数学提供介绍性的综述。所涵盖的内容主要针对初学者，所以在本书中有大量带有详细解释的例子、定义、定理、证明等（它们单独编号，并且用一个实心黑方块来表示其结束）。另外，考虑到面对的是初学者，因此对于每个证明，也都提供了足够详尽的过程。

这本教材力争达到以下目标：

1. 为大学二年级到大学三年级的学生介绍离散方法与组合推理的主题和技术。计数问题需要对结构（例如，是否与顺序有关以及是否允许重复）和逻辑可能性进行仔细分析，还可能是针对某种情况的存在性问题。经过仔细分析以后，我们常常会发现一个问题的求解通常是采用这样的方法：将给定问题分解成较小的子问题，然后计数每个可能的结果，最后再将各个子问题的解合并起来。

2. 介绍广泛的应用。在这一点上，如果需要数据结构（属于计算机科学）或者抽象代数的结构，那么只介绍所需的基本理论。此外，一些应用问题的解本身是迭代的过程，所以本教材将其写成特定的算法形式。求解问题的算法方法在离散数学中是很基本的，并且这种方法加强了这一学科与计算机科学领域的联系。序言离散数学与组合数学（第5版）

3. 通过学习这一不同于微积分以及差分方程等传统内容的知识，以增强学生的数学完备性。例如，有机会采用多种方法来计数一个特定的物品集合以建立一个结论。这就提供了所谓的组合恒等式，它也给出了一种新的证明方法。在这一版中的第2章介绍了证明的本质以及一个有效推理的构成，同时还引入了逻辑定律和推理规则。这部分的内容广泛，需要（基础薄弱的）学生牢记（对于学过逻辑课程或相关课程的读者来说，可以略过这些内容而不会有阅读困难）。第4章中介绍了利用数学归纳法（以及递归定义）进行证明，并且在以后的章节中广泛使用。

关于定理以及它们的证明，在许多情况下，都是通过分析特例来提出定理。另外，如果一个结论对于有限情况成立但对于无限情况不成立，那么就会指出这种情况以引起注意。过长的证明或者极其特殊的证明并没有在这里给出。但是，对于所省略的极少数证明过程，感兴趣的读者可以查阅每章后面列出的参考文献，将会看到这些结论都是成立的（对证明的强调程度取决于每个教师的目标以及学生们的知识程度）。

4. 为计算机科学专业的学生提供足够的基础知识。这些学生将会学到更多课程，比如数据结构、计算机语言理论以及算法分析。这里有关群、环、域以及布尔代数的知识也可以为数学专业的学生提供应用性的介绍，这有利于对抽象代数的继续学习。

使用这本教材的先决条件是读者应具有高中数学知识，并且有处理和解决各种各样问题的兴趣。不需要具备特别的编程能力，因为程序段和过程以伪代码的形式给出，并且这样设计和解释它们是为了解决特定的例子。至于微积分，我们将在序言的后面提到在第9章和第10章中所需掌握它们的程度。

我写本书前四版的主要动力来自于多年来所收到的学生和同事们，以及许多使用过本书前四版的不同大学和学院的学生和教师们的鼓励。这四版反映了我以及我的学生们的兴趣和关心之处，同时还参考了大学数学课程委员会以及计算机学会提出的建议。第5版继续按照相同的思路，并且反映了教师们特别是使用过或者正在使用第4版的学生们的意见和建议。本书特点

以下是这一最新版的一些主要特点的简要描述。这样的设计是为了帮助读者（学生或者其他人）学习好离散数学与组合数学的基础知识。

强调算法及应用。纵观本书，在许多领域中都给出了算法和应用。例如：

1. 第1章的一些例子中包括需要了解的计数方面的主题——特别是其中一个例子，说明了重复计数问题。

2. 第5章的第7节简介了计算复杂性。然后在这一章中的第8节使用了这个知识来分析一些基本伪代码程序的运行次数。

3. 第6章的内容包括语言和有限状态机。这就为读者介绍了计算机科学中的一个重要领域——计算机语言理论。

4. 第7章和第12章包括以下应用和算法的讨论：拓扑排序以及被称为深度优先搜索和宽度优先搜索的搜索技术。

5. 第10章主要讨论递推关系。其内容包括了以下方面的应用： (a)冒泡排序； (b)二分查找； (c)斐波纳契数； (d)Koch雪花； (e)哈斯图； (f)栈的数据结构； (g)二元树；(h)拼砌。

6. 第16章介绍了称为群的代数结构的基本性质。这里的内容说明了这种结构如何用于代数编码理论的研究，以及如何用于需要用到Polya计数法的计数问题。

解释详细。无论是一个例子还是一个定理的证明，对于它们的解释都仔细且全面。采取这种表示方法的主要目的是为了提高那些初次接触这种知识类型的读者的理解力。

练习。在每本数学教材中，练习都是非常重要的。花在练习上的时间在很大程度上影响着课程的进度。根据听课学生的兴趣以及数学功底，教师可以自行掌握用于课堂练习的时间。

在这17章中有1900多道练习。它们出现在相应章节的后面，一般按照每节中所介绍内容的顺序来安排。这些练习被设计为(a)复习本节中的基本概念； (b)与本章中前面各节所介绍的思想联系起来； (c)介绍与本节中内容有关的一些附加概念。一些练习要求设计一个算法或者写出一个计算机程序，常常是解决一个一般问题的特例。这些通常需要有一点编程经验。

每一章都有一个补充练习。它们为本章中提到的思想提供了进一步的回顾，并且同时还要用到前面一些章中介绍的知识。

本书最后提供了几乎所有奇数编号习题的答案。

各章小结。每章的最后一节都给出了一个本章主要思想的小结和历史回顾。目的是对于本章中的内容进行简单总结，并提供进一步学习和应用的参考信息。这种深入学习可以通过查阅列在每章后面的文献得以轻易实现。

特别是，第1，5，9章末尾的小结中包括这三章所给出计数公式的表。这些表有的还包括前面章节中的结论，目的是进行比较并说明新结论是如何推广前面结论的。内容安排

离散数学与组合数学对于大学课程来说是一个比较新的内容，所以在这些课程里需要学习哪些内容可以有多种选择。每位教师和每名学生都可能有各自的兴趣，因此，为满足作为一门综述性课程的要求，本教材包括的内容相当广泛。但是一些读者有可能感觉到应该包括一些更深入的知识。此外，对于本教材中所列出某些主题的顺序，也许还存在一些不同观点。

本教材始终强调用于问题求解的算法的本质和重要性。有关问题求解的思想和方法在计数和结构的相互作用下得以强化，并且计数和结构这两个主题为本教材所介绍的知识提供了一条主线。

本教材的内容分成四个部分。前七章是本书的基础核心，给出了离散数学的基本知识和原理。这第一部分足以作为一个季度或者一个学期的离散数学课程。第2章的内容为具有逻辑基础的读者提供了一个回顾。对于那些对证明感兴趣的读者来说，这部分的内容应该仔细阅读。第二门课程——重点在组合数学——应该包括第8、9、10章(若时间允许，还要包括第16章的1、2、3、10、11、12节)。第9章需要用到微积分里的一些知识；即求导和部分分式分解的基本内容。但是，对于那些希望略过这一章的读者来说，还是要看一下第10章的1、2、3、6、7节。重点放在有限图理论及其应用的课程，应该包括第11、12、13章。这三章组成了本教材的第三个主要部分。讲授应用代数的课程，应该包括第14、15、16、17章(这是第四部分，也是最后一部分)，这一部分讨论代数结构——群、环、布尔代数、域——并包括在密码学、开关函数、代数编码理论以及组合设计方面的应用。最后，强调离散结构在计算机科学中的作用的课程，应该包括第11、12、13、15章以及第16章的第1～9节。其中包括在以下各方面的应用：开关函数、RSA密码系统、代数编码理论、图论和树以及它们在最优化中扮演的角色。

考虑如下各章的依赖性，还可以开设其他课程。章号 依赖于前面的章节      1                  不依赖      2                  不依赖（所以讲授离散数学课程的教师，既可以从逻辑开始讲起，也可以从计数开始讲起）      3                  1，2  4                  1，2，3      5                  1，2，3，4      6                  1，2，3，5（其中还有6.1节依赖于4.1和4.2节）  7                  1，2，3，5，6（其中还有7.2节依赖于4.1和4.2节）      8                  1，3（其中还有例8.6依赖于5.3节）  9                  1，3 10                  1，3，4，5，9（其中还有例10.33依赖于7.3节） 11                  1，2，3，4，5（尽管一些图论思想已经在第5、6、7、8、10章中提到了，但是这一章关于图论的内容不依赖于前面的结论）     12                  1，2，3，4，5，11     13                  3，5，11，12     14                  2，3，4，5，7（在14.3节中用到欧拉phi函数()。这个函数在8.1节的例8.8中导出，但是在第14章中可以直接使用这个结论而不用查阅整个第8章） 15                  2，3，5，7 16                  1，2，3，4，5，7 17                  2，3，4，5，7，14第5版的变化

在本书的第5版中，采纳了使用过这本教材前几版的教师和学生们的意见和建议。与前四版一样，第5版的基调和意图保持不变。作者的目的仍是：为初学的学生或读者提供一种合理的、易读的、可理解的有关离散数学与组合数学的知识介绍。在第5版中有以下几点变化：

 在1.4节里现在包括关于游程的知识，这是出现在统计学研究中的一个概念——特别是，在质量控制领域中。

  2.3节的习题13中介绍了称为归结法的推理规则，这种规则被用来作为开发自动推理系统所需计算机程序的基础。

  本教材的前几个版本包括介绍概率的一节。现在扩展了这一节并增加了可选的三节，以满足想要深入研究与离散概率相关思想的读者需求——特别是，概率公理、条件概率、独立、贝叶斯定理以及离散随机变量。

  7.3节关于偏序和全序的内容现在包括一个可选例子，其中出现了Catalan数。

  在8.1节中的介绍性内容已经被重写，以提供从3.3节中的计数和文氏图到称为容斥原理的更普遍技术的过渡，使得这部分的知识更易被读者理解。

  离散数学与组合数学的一个吸引人的特点就是对于一个给定问题通常有各种解法。在第4版（第1章和第3章）中读者会看到，在两种情况下，都可以得到一个正整数n有2n-1种合成方式——即有2n-1种方式可以把n写成一个由若干正整数被加数组成的有序和形式。这个结论现在按照另外三种方式来建立： (i)在第4章中利用数学归纳法原理； (ii)在第9章中利用生成函数； (iii)在第10章中通过求解一个递推关系。

  对于那些想要了解关于离散概率更多内容的读者，可阅读9.2节，其中包括了一个处理几何随机变量的例子。

  10.2节现在包括了对Gabriel Lamé所做工作的一个讨论，他估计了在欧几里德算法中为找到两个正整数的最大公因子所需做的除法次数。

  在10.6节的一个练习中，介绍了Master定理及在算法分析中的重要性。

 关于运输网络的知识(13.3节)现在已更新，并且在最初由Lester Ford和Delbert Fulkerson开发的程序中加入了EdmondsKarp算法。

  14.3节关于模算术的内容,现在包括讨论线性同余伪随机数生成器的应用、私密密钥密码系统以及模的幂运算。进一步，在14.4节中，讨论了中国剩余定理，这在之前的版本中只进行了叙述，现在给出了这个结论的一个证明以及一个例子以说明如何应用这个定理。

  16.4节是新的可选内容。它介绍了RSA公开密钥密码系统，并说明了如何应用本教材前面章节中所开发的某些理论结果。

  与第2、3、4版一样，这一版下了很大功夫来更新每章末尾的小结和历史回顾。因此，给出的新文献和新版本更恰当。

  对于这第5版，在一些章的小结和历史回顾中加入了以下图片和照片：在第3章中加入了贝叶斯(Thomas Bayes)的图片以及柯尔莫哥洛夫(Andrei Nikolayevich Kolmogorov)的照片；在第4章中加入了AlKhowrizm的图片；在第12章中加入了David A.Huffman 的照片；在第13章中加入了Joseph B. Kruskal的照片。辅助

  采用这本教材作为课本的教师,如果需要本书17章以及三个附录中所有练习的解答或答案，请与longqm@163.com联系。

  下面的网址提供了学习离散数学与组合数学的更多资料。此外，它也提供了联系作者的方式，以供读者做出评论，提出建议，或者指出找到的错误之处：

www.aw.com/grimaldi致谢

如果篇幅允许，我将提到在写这本教材的第5版时对我提供帮助和鼓励的每一位学生。他们的建议帮助我去掉了许多错误以及含糊不清的内容，由此改进了整本教材的叙述水平。在这些学生中，特别要感谢Paul Griffith, Meredith Vannauker, Paul Barloon, Byron Bishop, Lee Beckham, Brett Hunsaker, Tom Vanderlaan, Michael Bryan, John Breitenbach, Dan Johnson, Brian Wilson, Allen Schneider, John Dowell, Charles Wilson, Richard Nichols, Charles Brads, Jonathan Atkins, Kenneth Schmidt, Donald Stanton, Mark Stremler, Stephen Smalley, Anthony Hinrichs, Kevin O’Bryant和Nathan Terpstra。

感谢Larry Alldredge, Claude Anderson, David Rader, Matt Hopkins, John Rickert和Martin Rivers对有关计算机科学内容的建议。感谢Barry Farbrother, Paul Hogan, Dennis Lewis, Charles Kyker, Keith Hoover, Matthew Saltzman和Jerome Wagner对一些应用的启发式评述。

衷心感谢AddisonWesley出版公司全体同仁（过去和现在）的热情与鼓励，特别要感谢Wayne Yuhasz, Thomas Taylor, Michael Payne, Charles Glaser, Mary Crittendon, Herb Merritt, Maria Szmauz, Adeline Ruggles, Stephanie Botvin, Jack Casteel, Jennifer Wall, Joanne Sousa Foster, Karen Guardino, Peggy McMahon, Deborah Schneider, Laurie Rosatone, Carolyn LeeDavis和Jennifer Albanese。特别是William Hoffman，RoseAnne Johnson和Barbara Pendergast，感谢他们为这第5版做出的杰出贡献。衷心感谢Steven Finch在校对本教材以及Paul Lorczak在检查练习答案精确性过程中所做的努力。

感谢我的同事John Kinney, Robert Lopez, Allen Broughton, Gary Sherman, George Berzsenyi, 特别是Alfred Schmidt，在我撰写这本或之前版本教材的整个过程中给予了关注和鼓励。

感谢对第1，2，3，4版，或者第5版教材的以下审阅者。

Norma E. AbelDigital Equipment Corporation

Larry AlldredgeQualcomm,Inc.

Charles AndersonUniversity of Colorado, Denver

Claude W. Anderson ⅢRoseHulman Institute of Technology

David ArnoldBaylor University

V.K.BalakrishnanUniversity of Maine at Orono

Robert BamhillUniversity of Utah

Dale BedgoodEast Texas State University

Jerry BeehlerTriState University

Katalin BencsathManhattan College

Allan BishopWestern Illinois University

Monte BoisenVirginia Polytechnic Institute

Samuel CouncilmanCalifornia State University at Long Beach

Robert CrawfordWestern Kentucky University

Ellen Cunningham, SPSaint MaryoftheWoods College

Care De VitoNaval Postgraduate School

Vladimir DrobotSan Jose State University

John DyeCalifornia State University at Northridge

Carl EckbergSan Diego State University

Michael FalkNorthern Arizona University

Marvin FreedmanBoston University

Robert GeitzOberlin College

James A. GlasenappRochester Institute of Technology

Gary GordonLafayette College

Harvey GreenbergUniversity of Colorado, Denver

Laxmi GuptaRochester Institute of Technology

Eleanor O.HareClemson University

James HarperCentral Washington University

David S. HartRochester Institute of Technology

Maryann HastingsMarymount College

W. Mack HillWorcester State College

Stephen HirtleUniversity of Pittsburgh

Arthur HobbsTexas A&M University

Dean HoffmanAuburn University

Richard IltisWillamette University

David P. JacobsClemson University

Robert JajcayIndiana State University

Akihiro KanamoriBoston University

John KonvalinaUniversity of Nebraska at Omaha

Rochelle LeigowitzWheaton College

James T.LewisUniversity of Rhode Island

YHsin LiuUniversity of Nebraska at Omaha

Joseph MalkevitchYork College(CUNY)

Brian MartensenThe University of Texas at Austin

Hugh MontgomeryUniversity of Michigan

Thomas MorleyGeorgia Institute of Technology

Richard OrrRochester Institute of Technology

Edwin P.OxfordBaylor University

John RausenNew Jersey Institute of Technology

Martin RiversLexmark International, Inc.

Gabriel RobinsUniversity of Virginia

Chris RodgerAuburn University

James H. SchmerlUniversity of Connecticut

Paul S. SchnareEastern Kentucky University

Leo SchneiderJohn Carroll University

Debra Diny ScottUniversity of Wisconsin at Green Bay

Gary E. StevensHartwick College

Dalton TarwaterTexas Tech University

Jeff TecoskyFeldmanHarvard University

W.L.TerwilligerBowling Green State University

Donald ThompsonPepperdine University

Thomas UpsonRochester Institute of Technology

W. D. WallisSouthern Illinois University

Larry WestVirginia Commonwealth University

Yixin ZhangUniversity of Nebraska at Omaha

特别感谢Clemson大学的Douglas Shier审阅了所有五个版本的手稿。也感谢Joan Shier请Doug审阅了第4版和第5版。

专用名词的解释归功于Northern Virginia Community大学的Yvonne Panaro博士。谢谢你，Yvonne，谢谢你，Patter (Patricia Wickes Thurston)，感谢你们在这个解释的过程中所起的作用。

这种篇幅的教材需要用到大量参考文献。在我需要书籍和文章时，RoseHulman理工大学图书馆的工作人员总是给予配合，所以感谢John Robson, Sondra Nelson, Dong Chao, Jan Jerrell, 特别是Amy Harshbarger和Margaret Ying所做出的努力。此外，感谢Keith Hoover和Raymond Bland解决了写作过程中出现的许多硬件问题。

最后，当然也是最重要的，再次感谢永远耐心并且始终持鼓励态度现已退休的RoseHulman数学系秘书——Mary Lou McCullough夫人。第五次谢谢你，Mary Lou，感谢你所做的所有工作！

作者再次声明，若仍有错误、含糊不清的内容，以及使人误解的论述，由作者一人负责。

 R.P.G.   于Terre Haute，印第安纳州