Introductory Combinatorics（组合数学英文版） Richard A.Brualdi.pdf-资料库

sowelo-5818375-4744300845397465266.pdf-第1页.png

第1页 / 共618页

sowelo-5818375-4744300845397465266.pdf-第2页.png

第2页 / 共618页

sowelo-5818375-4744300845397465266.pdf-第3页.png

第3页 / 共618页

sowelo-5818375-4744300845397465266.pdf-第4页.png

第4页 / 共618页

sowelo-5818375-4744300845397465266.pdf-第5页.png

第5页 / 共618页

sowelo-5818375-4744300845397465266.pdf-第6页.png

第6页 / 共618页

sowelo-5818375-4744300845397465266.pdf-第7页.png

第7页 / 共618页

sowelo-5818375-4744300845397465266.pdf-第8页.png

第8页 / 共618页

English reprint edition copyright © 2009 by Pearson Education Asia Limited and China Machine Press. Original English language title: Introductory Combinatorics, Fifth Edition (ISBN 978-0-13-602040-0) by Richard A. Brualdi, Copyright © 2010, 2004, 1999, 1992, 1977 by Pearson Education, Inc. All rights reserved. Published by arrangement with the original publisher, Pearson Education, Inc., publishing as Prentice Hall. For sale and distribution in the People's Republic o( China exclusively (except Taiwan, Hong Kong SAR and Macau SAR). *=I'1*:Jc~EP Jlti EI3 Pearson Education Asia Ltd·tf&,fJL,j;jI~ t±:I Jlti1±5!1l;R t±:I Jlti 0 *~t±:IJlti.=I'100W~,~~QffM~~~~~~.*=I'1~~o &.~~$A~*~OO~~(~~M~OO~m .• nM~fiROC~~OO~~ it!! OC) ti'f ~ :& 1']- 0 *=I'1t-tOOm6:ftPearson Education (:I:.g:1::~l'l' t±:IJlti~ffi) i*:J't!)jjffJfu;~, 7Cfu;~ .~l~ti'f~o Jl&tJlJiJf~, ~tJl!lO~o *~*~~~ ~.*~~~~~.JiJf *~JI&~~ia~: 111*: 01-2009-1361 III ~ ;ffJl&~ ~ ( CIP) ~. tfl~~~ (~:JcJlti . ~5Jlti) / (~) :;flJ'l-j@ (Brualdi, R. A.) if. -~~*: ,fJL lJItI~t±:IJlti1±, 2009.3 ( ~ ~ Iffi Jlti =1'1 J! ) =I'1~Iffi:Jc: Introductory Combinatorics, Fifth Edition ISBN 978-7-111-26525-2 I. tfl··· II. :;flJ... m. tfl~~~-~M-~:Jc IV. 0157 ,fJL,j;jI~t±:IJlti1± (~tffir!T]l!iJ;&1K ~iJJ!l:*m22% iI!~i&tli!~ l00037) ~ff~m: iKtJHF ~Lrjc.?~QiIlEP ~:ff.0iil f1111: lj 2009if-3 j} ~ lJlti~ I & Ep,\jlIJ 150mm x 214mm • 19.375EPStt fu;lt=l'1%: ISBN 978-7-111-26525-2 JEff)-: 49.00jC

~~~~0.,.lli~*~n~M~~~~m~~~*~m,~fi~ OO~a~Mn~~~~~~*~T£.ft~~.,~~A~~~ffl.,~ ~OOamAtt*~B~~+~~~£~~lli.~~m~oaft~~~*~ ~, ~OO~~~~~~~~~*~~*~~~,rr.m~n~~~~*w ~t41i'fl1Jt~~H4liJf;fo~~~l\llltrti, B3Jltffij~1:.~~~n~~f'F, /Ff)(. ~TliJf~~m_,~.ffiT~*~.~, ~.oo~*~m,x~~~~~ ft,~~m*/F~~~fl~~~ffij~~o ~~,a~*mA~*.~.~~,fiOO~rr.m~~~Bili~,~ ~~A~~.*B~~mo~~rr.m~~~~lli~~W~Am~,~A .~;ffij*~~M~.~a~~~.~R~*~Q.oafioomAtt*~ BIJt~~5~~~~, ~oo~~~oo~a~rr.mn~~B~A+$~~ iJE;fo~B~g2~~MfJJ~it~f1i1~ft~z~o ~Jlt, 51*-1!tOOj~~3'Ht .m~M~~fiOOrr.m~~.~~~B~~~m~.~~m,~A~~ ~~~ .• ~~~~~~-~*~~~B3Z~o m;ffllI~lli~U~~7H±~1f.~iR¥1j "lli~~7-J~~nli97" 0 ~ 1998$ *M,~~~U.~I~.~~aT~~.8~OO~~~~M~o~M~ ~~/F1f&r~jJ, fi1f1~Pearson, McGraw-Hill, Elsevier, MIT, John Wiley & Sons, Cengage~~~~£lli~0-i'f].iz:.T~tff~~f'F**, hAft!? 1f1~~~~5(Bf!tt~Mq:tft~lliAndrew S. Tanenbaum, Bjarne Stroustrup, Brain W. Kernighan, Dennis Ritchie, Jim Gray, Afred V. Aho, John E. Hopcroft, Jeffrey D. Ullman, Abraham Silberschatz, William Stallings, Donald E. Knuth, John L. Hennessy, Larry L. Peterson~*~iP£~~-1!tg2 ~~~, 0"rr.mn~~~"7-J~.lli~,m~~~~.liJf~&$.o *m~ttm~MW,~~*~T~~~~~~~~ •• o "~.mn~~~"~lli~I~~~TOO~~~~~~jJ.M, OO~~ ~~/Ff)(.mT~~~~.m%,~/Fff~~~mffTn~~$~~I

iv ~;ffi~~~~~&~~~~~~~~~~~fflM, ~~ffi~~~~~~ ~~*~*.~+, "~.mn~M~" B~lli~T~~N~~~, ~® ~M~~~~W~T~H~Q~,#.W$~~*m~~~.M~#~~ M. ~~~~"~A~~~$"~~~~.& •• *.$~.~m.~ ~~~JlJT*m. ~~~~~. ~A~.M. -~~~~. F.~$~.ME~~., ~®~.~fim~OO~~T~~~*~.~.~.mn~~tt*~~~M .~~~.~.~.M&*~~.~~, .. ~~~*~.m.M~.* ~~m~~~A-~~~~~,fim~§~~~~~~, ~&~~.m~ ~fim~~~-~.§~~.~moo.~.~tl~~~~~~~~fim~ I~.lli.~~~~m~, fim~G~~~~T: $~[XJgj}~: www.hzbook.com Eg T~Ht: hzjsj@hzbook.com .IIHj~Eg1.~: (010) 88379604

I have made some substantial changes in this new edition of Introductory Combi natorics, and they are summarized as follows: Preface 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 Chap ter 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 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 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 under gone 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.

Vi Preface 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 car 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. I 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 coefficients, and Chapter 6 covers the inclusion-exclusion principle. The section on Mobius 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 Schroder numbers. One could stop at the end of any section of this chapter. The chapters that follow Chapter 8 are

Preface Vll 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 10 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 14 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 cour~e 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 P6lya'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 D. 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 en thusiasm 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 refer ences 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. I am very grateful to many individuals who have given me comments on previous editions and for this edition, including the discovery of typos. These individuals in clude, in no particular order: Russ Rowlett, James Sellers, Michael Buchner, Leroy F. Meyers, Tom Zaslavsky, Nils Andersen, James Propp, Louis Deaett, Joel Brawley. Walter Morris, John B. Little, Manley Perkel, Cristina Ballantine, Zixia Song, Luke Piefer, Stephen Hartke, Evan VanderZee, Travis McBride, Ben Brookins, Doug Shaw, Graham Denham, Sharad Chandarana, William McGovern, and Alexander Zakharin. Those who were asked by the publisher to review the fourth edition in preparation for this fifth edition include Christopher P. Grant who made many excellent comments. Chris Jeuell sent me many comments on the nearly completed fifth edition and saved me from additional typos. Mitch Keller was an excellent accuracy checker. Typos, but I hope no mistakes, probably remain and they are my responsibility. I am grateful to everyone who brings them to my attention. Yvonne Nagel was extremely helpful in solving a difficult problem with fonts that was beyond my expertise.

资料库

Introductory Combinatorics（组合数学英文版） Richard A.Brualdi.pdf

相关推荐

课程资源

热门标签

最新资料