组合数学
2009-3
机械工业出版社
Richard A.Brualdi
605
无
I have made some substantial changes in this new edition of Introductory Combinatorics， and they are summarized as follows: In Chapter 1, a new section （Section 1.6） on mutually overlapping circles has been added to illustrate some of the counting techniques in later chapters. Previously the content of this section occured in Chapter 7. The old section on cutting a cube in Chapter 1 has been deleted, but the content appears as an exercise. Chapter 2 in the previous edition （The Pigeonhole Principle） has become Chapter 3. Chapter 3 in the previous edition, on permutations and combinations, is now Chapter 2. Pascals formula, which in the previous edition first appeared in Chapter 5, is now in Chapter 2. In addition, we have de-emphasized the use of the term combination as it applies to a set, using the essentially equivalent term of subset for clarity. However, in the case of multisets, we continue to use combination instead of, to our mind, the more cumbersome term submultiset. Chapter 2 now contains a short section （Section 3.6） on finite probability. Chapter 3 now contains a proof of Ramseys theorem in the case of pairs. Some of the biggest changes occur in Chapter 7, in which generating functions and exponential generating functions have been moved to earlier in the chapter （Sections 7.2 and 7.3） and have become more central. The section on partition numbers （Section 8.3） has been expanded. Chapter 9 in the previous edition, on matchings in bipartite graphs, has undergone a major change. It is now an interlude chapter （Chapter 9） on systems of distinct representatives （SDRs）——the marriage and stable marriage problemsand the discussion on bipartite graphs has been removed. As a result of the change in Chapter 9, in the introductory chapter on graph theory （Chapter 11）, there is no longer the assumption that bipartite graphs have been discussed previously.
本书是系统阐述组合数学基础、理论、方法和实例的优秀教材，出版30多年来多次改版，被MIT、哥伦比亚大学、UIUC、威斯康星大学等众多国外高校采用，对国内外组合数学教学产生了较大影响，也是相关学科的主要参考文献之一。 本书侧重于组合数学的概念和思想。包括鸽巢原理、计数技术、排列组合、P61ya计数法、二项式系数、容斥原理、生成函数和递推关系以及组合结构（匹配、实验设计、图）等。深入浅出地表达了作者对该领域全面和深刻的理解。除包含第4版中的内容外，本版又进行了更新，增加了有限概率、匹配数等内容。此外，各章均包含大量练习题，并在书末给出了参考答案与提示。
Richard A．Brualdi美国威斯康星大学麦迪逊分校数学系教授（现已退休），曾任该系主任多年。他的研究方向包括组合数学、图论、线性代数和矩阵理论．编码理论等。Brualdi教授的学术活动非常丰富，担任过多种学术期刊的主编。2000年由于“在组合数学研究中所做出的杰出终身成就
Preface1 What 'Is Combinatorics? 1.1 Example: Perfect Covers of Chessboards 1.2 Example: Magic Squares 1.3 Example: The Four-Color Problem 1.4 Example: The Problem of the 36 OfFicers 1.5 ,Example: Shortest-Route Problem 1.6 Example: Mutually Overlapping Circles 1.7 Example: The Game of Nim 1.8 Exercises2 Permutations and Combinations 2.1 Four Basic Counting Principles 2.2 Permutations of Sets 2.3 Combinations (Subsets) of Sets 2.4 Permutations of Multisets 2.5 Combinations of Multisets 2.6 Finite Probability 2.7 Exercises3 The Pigeonhole Principle 3.1 Pigeonhole Principle: Simple Form 3.2 Pigeonhole Principle: Strong Form 3.3 A Theorem of Ramsey 3.4 Exercises4 Generating Permutations and Combinations 4.1 Generating Permutations 4.2 Inversions in Permutations 4.3 Generating Combinations 4.4 Generating r-Subsets 4.5 Partial Orders and Equivalence Relations 4.6 Exercises5 The Binomial Coefficients 5.1 Pascal's Triangle 5.2 The Binomial Theorem 5.3 Unimodality of Binomial Coefficients 5.4 The Multinomial Theorem 5.5 Newton's Binomial Theorem 5.6 More on Partially Ordered Sets 5.7 Exercises6 The Inclusion-Exclusion Principle and Applications 6.1 The Inclusion-Exclusion Principle 6.2 Combinations with Repetition 6.3 Derangements 6.4 Permutations with Forbidden Positions 6.5 Another Forbidden Position Problem 6.6 M6bius Inversion 6.7 Exercises7 Recurrence Relations and Generating Functions 7.1 Some Number Sequences 7.2 Generating Functions 7.3 Exponential Generating Functions 7.4 Solving Linear Homogeneous Recurrence Relations .. 7.5 Nonhomogeneous Recurrence Relations 7.6 A Geometry Example 7.7 Exercises8 Special Counting Sequences 8.1 Catalan Numbers 8.2 Difference Sequences and Stirling Numbers 8.3 Partition Numbers 8.4 A Geometric Problem 8.5 Lattice Paths and Schr6der Numbers 8.6 Exercises9 Systems of Distinct Representatives10 Combinatorial Designs11 Introduction to Graph Theory12 More ONgraph Theory13 Digraphs and Networks14 Polya CountingAnswers and Hints to ExercisesBibliographyIndex
Chapter 3 The Pigeonhole Principle We consider in this chapter an important， but elementary, combinatorial principle that can be used to solve a variety of interesting problems, often with surprising conclusions. This principle is known under a variety of names, the most common of which are the pigeonhole principle, the Dirichlet drawer principle, and the shoebox principle.1 Formulated as a principle about pigeonholes, it says roughly that if a lot of pigeons fly into not too many pigeonholes, then at least one pigeonhole will be occupied by two or more pigeons. A more precise statement is given below. 3.1 Pigeonhole Principle: Simple FormThe simplest form of the pigeonhole principle is tile following fairly obvious assertion.Theorem 3.1.1 If n+1 objects are distributed into n boxes, then at least one box contains two or more of the objects. Proof. The proof is by contradiction. If each of the n boxes contains at most one of the objects, then the total number of objects is at most 1 + 1 + ... +1（n ls） = n.Since we distribute n + 1 objects, some box contains at least two of the objects. Notice that neither the pigeonhole principle nor its proof gives any help in finding a box that contains two or more of the objects. They simply assert that if we examine each of the boxes, we will come upon a box that contains more than one object. The pigeonhole principle merely guarantees the existence of such a box. Thus, whenever the pigeonhole principle is applied to prove the existence of an arrangement or some phenomenon, it will give no indication of how to construct the arrangement or find an instance of the phenomenon other than to examine all possibilities.
无
这本书是老师推荐使用的组合数学教材,因为经典所以修版这么多次,而且原版的英文教材读起来很带感.再加上组合数学本身所教授的内容就比一般的数学专业知识有趣,因此此书是很值得尝试学习的.
我个人很喜欢国外的书，这本书明理清晰易懂，是组合数学，计算机，离散数学等方面的不可或缺的参考书。我个人是图论专业
有一层塑料皮包着 不错 这个第五版是网上最流行的组合数学版本了
最经典的组合教材，出自大家之手，能把看似复杂的问题解释的简明透彻，所谓站的高看的远。
适合高中及大学数学入门·
全英文版，摸起来很有感觉，能激发学数学的兴趣。。
学数学看英文两不误，非常好。
不管是对数学还是计算机科学有兴趣的都应该读一读。高中生有条件的都可以读
虽是英文版，但比较易懂，讲得很详细，例子也多
经典书，拜读ing，其实不大适合学计算机的人看
书是一本好书，就是还没有时间看
还是看原版书，印刷质量还可以，除了字体有点小之外。
纸张有点薄，有些页感觉有点透。不过书是非常好的书，推荐~
讲的非常的基础，是学习算法的必读书。
要有一定的英文基础，提高思维能力的好书
放在案头，慢慢学习，原著经典，永垂不朽。
书本身没有问题，人的问题
死书本新，外观好
是正版的，但印刷差了点
忘记确认收到货了，对不起
给儿子买的，老师要求买的。
书很不错，对我的数学英语是个锻炼的机会
计算基础书籍 必须看
提供内功的好书
英文不行的不要买了
英文的好东西多啊
很不错的一本书，而且纸质也很不错的。。买回来好好看看。。
虽然没有看完.不过就看的东西来说.还是很不错的
书还是很好的 但是到货的时间太长了 我等的都有点不耐烦了 希望下次能够早点到
计算机必学的数学
组合数学（英文版 第5版）
：组合数学（英文版 第5版）
学习组合数学的一本好书
1.看了这本书后，我才真正意识到，数学是经验科学。
2.这书不适合自学，里面牵涉太多数学学科，一般大学那点数学基础肯定不够用。网上有北京师范大学用这本书上课的视频，讲得灰常好，就是省去了好几章内容以及后面的整个图论部分。
3.这书其实不怎么样（除非只把它当作大学数学专业的教科书）。要是没有北师大的视频，也就只能玩玩计数。
鸽笼原理，容斥原理，Nim博弈，Catalan数等等，都是很经典的，这本书和《算法导论》一起买很合适，尤其用来针对算法学习。
首先，不得不说这是一本好书，但是翻译实在是不敢恭维~~ 怀着膜拜的心情把这本书买了回来，发现翻译得真够烂的。我刚看到第9页，后面的不知道翻译的怎么样，但就描述幻方构造方法的步骤部分来说，翻译得确实够烂的，我看了三遍都没看懂！ 对照了一下英文版的，一下子就看懂了，我不知道是我语文没学好还是翻译的确实够烂的~
举例来说"其后的整数沿着自左下至右上的这条对角线按照自然顺序放置"读起来就很别扭，"这条"是指那条？被指代的部分还没出现呢，代词就冒出来了呀~ 难道朱自清要把"弯弯曲曲的荷塘上面"改成"弯弯曲曲的这个荷塘上面不成"?
还有第6页的最下面一行 "当前要摆放的整数将放在紧挨上述位置的下方"，我看了半天，也没看到"上述位置"是指上面说的哪个位置，虽说数学很抽象，不至于要抽象到这个地步吧？？看人家原文是怎么写的"The next integer is placed in the square immediately below the last square that was filled.",设法把last square翻译准确点不就好了？其实这句后面省略了"with the last integer"。翻译出来就是”当前要摆放的整数将直接放在上一个整数摆放位置的下方"，immediately在这里表示"直接的"。
如果已经买了的朋友，幻方构造方法步骤这部分也没看懂的话，这里有个演示可以帮助理解：
http://britton.disted.camosun.bc.ca/magicsq/magic.html
“现在考虑你所喜爱的这个城镇里的居民，在一对相爱的人之间连上一条线，就得到了图的另一个例子。但你要承认这样的事实：有时一个人对另一个人的爱，并不总是能够得到对方的回报”——Richard A. Brualdi，Introdutory Combinatorics（组合数学），机械工业出版社，2005，中译版292页
二零零六年不见的东西可以列成一张长长的单子，但是在那一年里我仍然保持着积极向上丢三拉四的革命乐观主义精神。我甚至乐呵呵地告诉每一个认识的朋友我曾经遗留下IKEA的水瓶、卫衣若干在大学城A3某多媒体教室，以此让大家知道我随和可亲，不会因为身外物的消失而改变世界观和价值理念。紧接着就是时间哗哗地流去，二零零七年即将结束，大家都在闹哄哄地打招呼，想扯住她的衣角留下一下话。我却再也找不回我的插座和风筝——这两件物事的遗失是今年的仅有，可我记忆犹新，耿耿于怀。
插座并没有特别之处，六插孔设计，三相电流流入。按下电源后显示器呲地一声亮起，犹如打开一扇窗口。往后每每到达现实场合，我有一加仑足够的笑脸来应酬诸位同仁，但却缺少一小勺的真诚心意——团队也好情感也罢。直到有一天，我接到电话，一端外是沉默的恳求，客观上说，我是责无旁贷，我拔下插座，把它装进背包，再一次搭上恶心公交，前往城市的另外一端去修理电脑。我以简单粗暴的方式完成后，把插座遗漏在现场。往后我羞于向此人要回这本属于我的财产，我似乎觉得，插座是被我故意抛弃在那儿的。也许我厚颜无耻地认定自己无辜于天地间。我的退出只应受到道德的谴责——而道德又价值几何呢？可它对我的惩罚是让我噩梦于寒冷的夜晚中，醒来后瑟缩在一角，想寻求帮助但发现诸位都已入眠。我桌面上从此就缺少了这一个插座，我要连接的时候总得把线绕过桌子，插在室友的插座上，这个时候我总会想起我的插座，也想到那件叫爱情的疯狂小事。不，这并不是小事，而非常重大，我已经暗中决定，从那日后破坏掉身体上一切与此相关的腺体和淋巴，让系统完蛋吧。
风起深夜，但华工大建筑野树林立，电杆丛生 ，根本容不下一只自制的风筝。但我最终见证这一伟业的完成。我左手举风筝右手做V字状的照片被保存下来——我承认那副尊容相当傻。但校学生会的大人们并不这么认为，他们在稍后把一等奖证书发给我。我欢天喜地地接过，欢天喜地地把风筝从西湖边捧到北湖边，欢天喜地地把风筝挂在床头。然而就在几个月后，我被告知要宿舍搬迁。我是在最后的一刻决定不带上这只风筝，而是把它遗留给肮脏的北九，很快就有校工来清理宿舍，很快风筝将被支离成尸体，手绘的彩纸将被撕碎，竹篾会被踩断成一截一截，在垃圾箱里没人会发现这团东西曾经是一只风筝，曾经被视为生日礼物，曾经寄托着许多许多许多不能明言的句子。你可能本来以为有风自可放飞，但是总有线缠来绕去，风筝总有一天会跌落在冰冷的路面上。风筝的真正丢失大概只是数日之前，结果黯然，我心神伤。我再一次认定自己是人形禽兽，决不可饶恕。但是事实已经如此。
插座和风筝并不算身边长物，但是我的二零零七因此而变得遗憾而感伤。新年即将降临，一切似乎重新开始，但是我总感到不知名的寒冷盘踞在身后某处，伺机偷袭。可能存在的庇护所几乎全部搬迁到关于一点对称的地球的某端，我的心智已经麻木在某个失落的地区。如果这不叫刻骨铭心，那又叫什么呢？
“作者语言幽默，例子浅显，是枯燥的数学专业课程里一道亮丽的风景，可以作为趣味数学读物，激发各位对数学的兴趣”——拉拉
“最后，再次感谢我亲爱的妻子Mona,是她给我的生活带来幸福、激情和勇气。”——Richard A. Brualdi
你被我发现了。
@Tanky Woo 请问这本书和 Kenneth H.Rosen 的 《离散数学及其应用》，针对学习算法来说，哪本更有帮助。
相比英文版，这个版本36军官问题中少了sudoku的举例，被省吃俭用了~
还有更可笑的翻译哦，书中第10页Nim取子游戏中”游戏法则如下：1) 游戏人交替进行游戏...“，无语，游戏规则怎么被翻译成游戏法则了？ 更可笑的是译者连玩家都不知道，把玩家翻译成了游戏人？？ 真够雷人的呀~ 哈哈哈
其实我觉得还行啦，只是不是那么完美，当然英文原版是最好的啦
“一个n阶图叫做完全图，如果他的任意一对不同顶点都构成一条边”
语序调整一下会死啊！
“自左下至右上的这条对角线”
其他不说，不过这句确实没问题。
先出现“以四为基底”，翻了几页才出现“以3为基底即3进制”这样的内容……
翻译书就看作者负责不负责了。。。很多都是懒省事。。有得干脆水平不行。。。烂的一B或者懒得一B。。。还是原版吧。。。哎。。。
从种种错误可以看出，，一者很大程度是依靠了机器翻译了。。。不是一点点对着翻译的。。。
这种书首先是自己的是这方面的砖家学者，然后还得认真负责。。。缺一不可。。。
尼玛~~~懒省事的B。。。一看就是。。。不负责任。。。
是啊，这本书要对着英文版看，中文版读起来拗口，而且有翻反的，晕的
我想随便一个学生认真翻译一下也会好的吧，就是他们要用翻译机器来翻译，然后自己调整字句，蒙混过关，欺骗读者，这就可弊可恨了。
唉。。。那请问组合数学中有哪些中文的书比较好呢？
确实是的,构造幻方部分很难懂,看了维基百科才懂了
这个在初中的时候，我姐姐当一个脑筋急转弯告诉了我。所以直接过。哈哈
Now consider the people in your favorite city. Run a string between each pair of people that like each other. You have another example of a graph. Recognizing the fact that sometimes one's fondness for another person is not always reciprocated, you may have to put arrows on your strings as you did for streets, with the result being a digraph.
不是想象的那么简单的，买了才知道。
剛剛考完這門課
哦。。。。。您在说啥呢。。。。
为了说明白有向图的概念，说得这么复杂，直接说，有时候爱一个人是单向，别人不一定爱你，就可以了。从英文来看，作者用词很文学化。