(特价书)组合数学(英文影印版.第5版)

    书籍
    数学书籍
本书是系统阐述组合数学基础、理论、方法和实例的优秀教材，出版30多年来多次改版，被MIT、哥伦比亚大学、UIUC、威斯康星大学等众多国外高校采用，对国内外组合数学教学产生了较大影响，也是相关学科的主要参考文献之一。.

本书侧重于组合数学的概念和思想，包括鸽巢原理、计数技术、排列组合，Polya计数法、二项式系数、容斥原理、生成函数和递推关系以及组合结构(匹配、实验设计、图)等，深入浅出地表达了作者对该领域全面和深刻的理解。除包含第4版中的内容外，本版又进行了更新，增加了有限概率、匹配数等内容。此外，各章均包含大量练习题，并在书末给出了参考答案与提示。...

Richard A．Brualdi美国威斯康星大学麦迪逊分校数学系教授(现已退休)，曾任该系主任多年。他的研究方向包括组合数学、图论、线性代数和矩阵理论、编码理论等。Brualdi教授的学术活动非常丰富，担任过多种学术期刊的主编。2000年由于“在组合数学研究中所做出的杰出终身成就”而获得组合数学及其应用学会颁发的欧拉奖章。...

Preface .
1 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 Exercises
2 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 Exercises
3 The Pigeonhole Principle
3.1 Pigeonhole Principle: Simple Form

　　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. Pascal's 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 nmltisets, 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 Ramsey's 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 problems--and 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.
　　The chapter on more topics of graph theory (Chapter 13 in the previous edition) has been moved to Chapter 12. A new section on the matching number of a graph (Section 12.5) has been added in which the basic SDR result of Chapter 9 is applied to bipartite graphs.
　　The chapter on digraphs and networks (Chapter 12 in the previous edition) is now Chapter 13. It contains a new section that revisits matchings in bipartite graphs, some of which appeared in Chapter 9 in the previous edition.
　　In addition to the changes just outlined, for this fifth edition, I have corrected all of the typos that were brought to my attention; included some small additions; made some clarifying changes in exposition throughout; and added many new exercises. There are now 700 exercises in this fifth edition.
　　Based on comments I have received over the years from many people, this book seems to have passed the test of time. As a result I always hesitate to make too many changes or to add too many new topics. I don't like books that have "too many words" (and this preface will not have too many words) and that try to accomodate everyone's personal preferences on topics. Nevertheless, I did make the substantial changes described previously because I was convinced they would improve the book.
　　As with all previous editions, this book can be used for either a one- or two-semester undergraduate course. A first semester could emphasize counting, and a second semester could emphasize graph theory and designs. This book would also work well for a one-semester course that does some counting and graph theory, or some counting and design theory, or whatever combination one chooses. A brief commentary on each of the chapters and their interrelation follows.
　　Chapter 1 is an introductory chapter; I usually select just one or two topics from it and spend at most two classes on this chapter. Chapter 2, on permutations and combinations, should be covered in its entirety. Chapter 3, on the pigeonhole principle, should be discussed at least in abbreviated form. But note that no use is made later of some of the more difficult applications of the pigeonhole principle and of the section on Ramsey's theorem. Chapters 4 to 8 are primarily concerned with counting techniques and properties of some of the resulting counting sequences. They should be covered in sequence. Chapter 4 is about schemes for generating permutations and combinations and includes an introduction to partial orders and equivalence relations in Section 4.5. I think one should at least discuss equivalence relations, since they are so ubiquitous in mathematics. Except for the section on partially ordered sets (Section 5.7) in Chapter 5, chapters beyond Chapter 4 are essentially independent of Chapter 4, and so this chapter can either be omitted or abbreviated. And one can decide not to cover partially ordered sets at all. t have split up the material on partially ordered sets into two sections (Sections 4.5 and 5.7) in order to give students a little time to absorb some of the concepts. Chapter 5 is on properties of the binomial coeffcients, and Chapter 6 covers the inclusion-exclusion principle. The section on MSbius inversion, generalizing the inclusion-exclusion principle, is not used in later sections. Chapter 7 is a long chapter on generating functions and solutions of recurrence relations. Chapter 8 is concerned mainly with the Catalan numbers, the Stirling numbers of the first and second kind, partition numbers and the large and small SchrSder numbers. One could stop at the end of any section of this chapter. The chapters that follow Chapter 8 are independent of it. Chapter 9 is about systems of distinct representatives (so-called marriage problems). Chapters 12 and 13 make some use of Chapter 9, as does the section on Latin squares in Chapter 10. Chapter t0 concerns some aspects of the vast theory of combinatorial designs and is independent of the remainder of the book. Chapters 11 and 12 contain an extensive discussion of graphs, with some emphasis on graph algorithms. Chapter 13 is concerned with digraphs and network flows. Chapter t4 deals with counting in the presence of the action of a permutation group and does make use of many of the earlier counting ideas. Except for the last example, it is independent of the chapters on graph theory and designs. ..
　　When I teach'a one-semester course out of this book, I like to conclude with Burnside's theorem, and several applications of it, in Chapter 14. This result enables one to solve many counting problems that can't be touched with the techniques of earlier chapters. Usually, I don't get to Pdlya's theorem.
　　Following Chapter 14, I give solutions and hints for some of the 700 exercises in the book. A few of the exercises have a * symbol beside them, indicating that they are quite challenging. The end of a proof and the end of an example are indicated by writing the symbol.
　　It is difficult to assess the prerequisites for this book. As with all books intended as textbooks, having highly motivated and interested students helps, as does the enthusiasm of the instructor. Perhaps the prerequisites can be best described as the mathematical maturity achieved by the successful completion of the calculus sequence and an elementary course on linear algebra. Use of calculus is minimal, and the references to linear algebra are few and should not cause any problem to those not familiar with it.
　　It is especially gratifying to me that, after more than 30 years since the first edition of Introductory Combinatorics was published, it continues to be well received by many people in the professional mathematical community.

　　插图：
　　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.