离散及组合数学

出版时间：2012-7  出版社：科学出版社  作者：Ralph P. Grimaldi  页数：962  字数：961250  
Tag标签：无  

内容概要

离散及组合数学（第五版）（英文影印版）内容主要由四部分组成：（1）基本离散结构，包括集合论与逻辑、函数与关系、语言与有限状态自动机；（2）组合数学，包括排列组合、容斥原理、生成函数、递推关系、鸽巢原理；（3）图论及其应用，包括图论基本知识、树、最优化与匹配；（4）现代应用代数，包括环论与模算术、布尔代数与交换函数、群、编码理论、波利亚计数方法、有限域与组合设计。
离散及组合数学（第五版）（英文影印版）可作为计算机、软件工程和电子类相关专业的本科生或研究生教材，也可供工程技术人员参考。

作者简介

作者:(美)Ralph P. Grimaldi

书籍目录

PART 1 Fundamentals of Discrete Mathematics1 Fundamental Principles of Counting1.1 The Rules of Sum and Product1.2 Permutations1.3 Combinations:The Binomial Theorem1.4 Combinations with Repetition1.5 The Catalan Numbers(Optional)1.6 Summary and Historical Review2 Fundamentals of Logic2.1 Basic Connectives and Truth Tables2.2 Logical Equivalence:The Laws of Logic2.3 Logical Implication:Rules of Inference2.4 The Use of Quantifiers2.5 Quantifiers,Definitions,and the Proofs of Theorems2.6 Summary and Historical Review3 Set Theory3.1 Sets and Subsets3.2 Set Operations and the Laws of Set Theory3.3 Counting and Venn Diagrams3.4 A FirstWord on Probability3.5 The Axioms of Probability(Optional)3.6 Conditional Probability:Independence(Optional)3.7 Discrete Random Variables(Optional)3.8 Summary and Historical Review4 Properties of the Integers:Mathematical Induction4.1 TheWell-Ordering Principle:Mathematical Induction4.2 Recursive Definitions4.3 The Division Algorithm:Prime Numbers4.4 The Greatest Common Divisor:The Euclidean Algorithm4.5 The Fundamental Theorem of Arithmetic4.6 Summary and Historical Review5 Relations and Functions5.1 Cartesian Products and Relations5.2 Functions:Plain and One-to-One5.3 Onto Functions:Stirling Numbers of the Second Kind5.4 Special Functions5.5 The Pigeonhole Principle5.6 Function Composition and Inverse Functions5.7 Computational Complexity5.8 Analysis of Algorithms5.9 Summary and Historical Review6 Languages:Finite State Machines6.1 Language:The Set Theory of Strings6.2 Finite State Machines:A First Encounter6.3 Finite State Machines:A Second Encounter6.4 Summary and Historical Review7 Relations:The Second Time Around7.1 Relations Revisited:Properties of Relations7.2 Computer Recognition:Zero-One Matrices and Directed Graphs7.3 Partial Orders:Hasse Diagrams7.4 Equivalence Relations and Partitions7.5 Finite State Machines:The Minimization Process7.6 Summary and Historical ReviewPART 2 Further Topics in Enumeration8 The Principle of Inclusion and Exclusion8.1 The Principle of Inclusion and Exclusion8.2 Generalizations of the Principle8.3 Derangements:Nothing Is in Its Right Place8.4 Rook Polynomials8.5 Arrangements with Forbidden Positions8.6 Summary and Historical Review9 Generating Functions9.1 Introductory Examples9.2 Definition and Examples:Calculational Techniques9.3 Partitions of Integers9.4 The Exponential Generating Function9.5 The Summation Operator9.6 Summary and Historical Review10 Recurrence Relations10.1 The First-Order Linear Recurrence Relation10.2 The Second-Order Linear Homogeneous Recurrence Relation with Constant10.3 The Nonhomogeneous Recurrence Relation10.4 The Method of Generating Functions10.5 A Special Kind of Nonlinear Recurrence Relation(Optional)10.6 Divide-and-Conquer Algorithms(Optional)10.7 Summary and Historical ReviewPART 3 Graph Theory and Applications11 An Introduction to Graph Theory11.1 Definitions and Examples11.2 Subgraphs,Complements,and Graph Isomorphism11.3 Vertex Degree:Euler Trails and Circuits11.4 Planar Graphs11.5 Hamilton Paths and Cycles11.6 Graph Coloring and Chromatic Polynomials11.7 Summary and Historical Review12 Trees12.1 Definitions,Properties,and Examples12.2 Rooted Trees12.3 Trees and Sorting12.4 Weighted Trees and Prefix Codes12.5 Biconnected Components and Articulation Points12.6 Summary and Historical Review13 Optimization and Matching13.1 Dijkstra恠 Shortest-Path Algorithm13.2 Minimal Spanning Trees:The Algorithms of Kruskal and Prim13.3 Transport Networks:The Max-Flow Min-Cut Theorem13.4 Matching Theory13.5 Summary and Historical ReviewPART 4 Modern Applied Algebra14 Rings and Modular Arithmetic14.1 The Ring Structure:Definition and Examples14.2 Ring Properties and Substructures14.3 The Integers Modulo n14.4 Ring Homomorphisms and Isomorphisms14.5 Summary and Historical Review15 Boolean Algebra and Switching Functions15.1 Switching Functions:Disjunctive and Conjunctive Normal Forms15.2 Gating Networks:Minimal Sums of Products:Karnaugh Maps15.3 Further Applications:Don恡-Care Conditions15.4 The Structure of a Boolean Algebra(Optional)15.5 Summary and Historical Review16 Groups,Coding Theory,and Polya恠 Method of Enumeration16.1 Definition,Examples,and Elementary Properties16.2 Homomorphisms,Isomorphisms,and Cyclic Groups16.3 Cosets and Lagrange恠 Theorem16.4 The RSA Cryptosystem(Optional)16.5 Elements of Coding Theory16.6 The Hamming Metric16.7 The Parity-Check and Generator Matrices16.8 Group Codes:Decoding with Coset Leaders16.9 Hamming Matrices16.10 Counting and Equivalence:Burnside恠 Theorem16.11 The Cycle Index16.12 The Pattern Inventory:Polya恠 Method of Enumeration16.13 Summary and Historical Review17 Finite Fields and Combinatorial Designs17.1 Polynomial Rings17.2 Irreducible Polynomials:Finite Fields17.3 Latin Squares17.4 Finite Geometries and Affine Planes17.5 Block Designs and Projective Planes17.6 Summary and Historical ReviewAppendix 1 Exponential and Logarithmic Functions A-1Appendix 2 Matrices,Matrix Operations,and Determinants A-11Appendix 3 Countable and Uncountable Sets A-23Solutions S-1

章节摘录

1Fundamental Principles of CountingEnumeration, or counting, may strike one as an obvious process that a student learns when .rst studying arithmetic. But then, it seems, very little attention is paid to further development in counting as the student turns to “more dif.cult” areas in mathematics, such as algebra, geometry, trigonometry, and calculus. Consequently, this .rst chapter should provide some warning about the seriousness and dif.culty of “mere” counting.Enumerationdoesnotendwitharithmetic.Italsohasapplicationsinsuchareasascodingtheory, probability and statistics, and in the analysis of algorithms. Later chapters will offersome speci.c examples of these applications.Asweenterthisfascinating.eldofmathematics,weshallcomeuponmanyproblemsthat areverysimpletostatebutsomewhat“sticky”tosolve.Thus,besuretolearnandunderstand the basic formulas — but do not rely on them too heavily. For without an analysis of each problem, a mere knowledge of formulas is next to useless. Instead, welcome the challenge to solve unusual problems or those that are different from problems you have encountered in the past. Seek solutions based on your own scrutiny, regardless of whether it reproduces what the author provides. There are often several ways to solve a given problem.1.1 The Rules of Sum and ProductOur study of discrete and combinatorial mathematics begins with two basic principles of counting: the rules of sum and product. The statements and initial applications of these rules appear quite simple. In analyzing more complicated problems, one is often able to break down such problems into parts that can be solved using these basic principles. We want to develop the ability to “decompose” such problems and piece together our partial solutions in order to arrive at the .nal answer. A good way to do this is to analyze and solve many diverse enumeration problems, taking note of the principles being used. This is the approach we shall follow here.Our .rst principle of counting can be stated as follows:TheRuleofSum:If a .rst task can be performed in mways, while a second task can be performed in nways, and the two tasks cannot be performed simultaneously, then performing either task can be accomplished in any one of m+nways.Chapter 1 Fundamental Principles of CountingNote that when we say that a particular occurrence, such as a .rst task, can come about in mways, these mways are assumed to be distinct, unless a statement is made to the contrary. This will be true throughout the entire text.Acollegelibraryhas40textbooksonsociologyand50textbooksdealingwithanthropology.EXAMPLE1.1By the rule of sum, a student at this college can select among 40 +50 .90 textbooks in order to learn more about one or the other of these two subjects.The rule can be extended beyond two tasks as long as no pair of tasks can occur simultane-ously. For instance, a computer science instructor who has, say, seven different introductory books each on C++, Java, and Perl can recommend any one of these 21 books to a student who is interested in learning a .rst programming language.EXAMPLE1.2The computer science instructor of Example 1.2 has two colleagues. One of these col-leagues has three textbooks on the analysis of algorithms, and the other has .ve such textbooks. If ndenotes the maximum number of different books on this topic that this instructor can borrow from them, then 5 ≤n≤8, for here both colleagues may own copies of the same textbook(s).EXAMPLE1.3The following example introduces our second principle of counting.Intryingtoreachadecisiononplantexpansion,anadministratorassigns12ofheremployees to two committees. Committee A consists of .ve members and is to investigate possible favorable results from such an expansion. The other seven employees, committee B, will scrutinize possible unfavorable repercussions. Should the administrator decide to speak to just one committee member before making her decision, then by the rule of sum there are 12 employees she can call upon for input. However, to be a bit more unbiased, she decides to speak with a member of committee A on Monday, and then with a member of committee B on Tuesday, before reaching a decision. Using the following principle, we .nd that she can select two such employees to speak with in 5 .7 .35 ways.EXAMPLE1.4TheRuleofProduct:If a procedure can be broken down into .rst and second stages, andifthereare mpossibleoutcomesforthe.rststageandif,foreachoftheseoutcomes, thereare npossibleoutcomesforthesecondstage,thenthetotalprocedurecanbecarried out, in the designated order, in mnways.The drama club of Central University is holding tryouts for a spring play. With six men and eight women auditioning for the leading male and female roles, by the rule of product the director can cast his leading couple in 6 .8 .48 ways.EXAMPLE1.5EXAMPLE1.6Here various extensions of the rule are illustrated by considering the manufacture of license plates consisting of two letters followed by four digits.1.1 The Rules of Sum and Producta) If no letter or digit can be repeated, there are 26 .25 .10 .9 .8 .7 .3,276,000 different possible plates. b) With repetitions of letters and digits allowed, 26 .26 .10 .10 .10 .10 .6,760,000 different license plates are possible. c) If repetitions are allowed, as in part (b), how many of the plates have only vowels (A, E, I, O, U) and even digits? (0 is an even integer.)EXAMPLE1.7Inordertostoredata,acomputer’smainmemorycontainsalargecollectionofcircuits,each of which is capable of storing a bit — that is, one of the binary digits 0 or 1. These storage circuits are arranged in units called (memory) cells. To identify the cells in a computer’s main memory, each is assigned a unique name called its address. For some computers, such as embedded microcontrollers (as found in the ignition system for an automobile), an addressisrepresentedbyanorderedlistofeightbits,collectivelyreferredtoasa byte.Using the rule of product, there are 2 .2 .2 .2 .2 .2 .2 .2 .28 . 256 such bytes. So we have 256 addresses that may be used for cells where certain information may be stored.A kitchen appliance, such as a microwave oven, incorporates an embedded microcon-troller. These “small computers” (such as the PICmicro microcontroller) contain thousands of memory cells and use two-byte addresses to identify these cells in their main memory. Such addresses are made up of two consecutive bytes, or 16 consecutive bits. Thus there are 256 .256 .28 . 28 . 216 .65,536 available addresses that could be used to iden-tify cells in the main memory. Other computers use addressing systems of four bytes. This 32-bit architecture is presently used in the Pentium. processor, where there are as many as 28 . 28 . 28 . 28 . 232 .4,294,967,296 addresses for use in identifying the cells in main memory. When a programmer deals with the UltraSPARC. or Itanium§ processors, he orsheconsidersmemorycellswitheight-byteaddresses.Eachoftheseaddressescomprises 8 .8 .64 bits, and there are 264 .18,446,744,073,709,551,616 possible addresses for this architecture. (Of course, not all of these possibilities are actually used.)EXAMPLE1.8At times it is necessary to combine several different counting principles in the solution of one problem. Here we .nd that the rules of both sum and product are needed to attain the answer.At the AWL corporation Mrs. Foster operates the Quick Snack Coffee Shop. The menu at her shop is limited: six kinds of muf.ns, eight kinds of sandwiches, and .ve beverages (hot coffee, hot tea, iced tea, cola, and orange juice). Ms. Dodd, an editor at AWL, sends her assistant Carl to the shop to get her lunch — either a muf.n and a hot beverage or a sandwich and a cold beverage.Bytheruleofproduct,thereare6 .2 .12waysinwhichCarlcanpurchaseamuf.nand hot beverage. A second application of this rule shows that there are 8 .3 .24 possibilities for a sandwich and cold beverage. So by the rule of sum, there are 12 +24 .36 ways in which Carl can purchase Ms. Dodd’s lunch..Pentium (R) is a registered trademark of the Intel Corporation..The UltraSPARC processor is manufactured by Sun (R) Microsystems, Inc. §Itanium (TM) is a trademark of the Intel Corporation.Chapter 1 Fundamental Principles of Counting1.2PermutationsContinuing to examine applications of the rule of product, we turn now to counting linear arrangements of objects. These arrangement sare of ten called permutations whentheobjects aredistinct.Weshalldevelopsomesystematicmethodsfordealingwithlineararrangements, starting with a typical example.In a class of 10 students, .ve are to be chosen and seated in a row for a picture. How manyEXAMPLE1.9such linear arrangements are possible?The key word here is arrangement, which designates the importance of order.If A,B,C, ...,I,Jdenotethe10students,thenBCEFI,CEFIB,andABCFGarethreesuchdifferentarrangements, even though the .rst two involve the same .ve students.To answer this question, we consider the positions and possible numbers of students we can choose from in order to .ll each position. The .lling of a position is a stage of our procedure.Each of the 10 students can occupy the 1st position in the row. Because repetitions are not possible here, we can select only one of the nine remaining students to .ll the 2nd position. Continuing in this way, we .nd only six students to select from in order to .ll the 5th and .nal position. This yields a total of 30,240 possible arrangements of .ve students selected from the class of 10.Exactly the same answer is obtained if the positions are .lled from right to left — namely, 6 .7 .8 .9 .10. If the 3rd position is .lled .rst, the 1st position second, the 4th position third, the 5th position fourth, and the 2nd position .fth, then the answer is 9 .6 .10 .8 .7, still the same value, 30,240.As in Example 1.9, the product of certain consecutive positive integers often comes into play in enumeration problems. Consequently, the following notation proves to be quite useful when we are dealing with such counting problems. It will frequently allow us to express our answers in a more convenient form.De.nition1.1For an integer n≥0, nfactorial (denoted n!) is de.ned by 0!.1,n!.(n)(n.1)(n.2)(3)(2)(1),for n≥1.One .nds that 1!.1, 2!.2, 3!.6, 4!.24, and 5!.120. In addition, for each n≥0, (n+1)!.(n+1)(n!).Before we proceed any further, let us try to get a somewhat better appreciation for how fast n!grows. We can calculate that 10!.3,628,800, and it just so happens that this is exactly the number of seconds in six weeks. Consequently, 11!exceeds the number of seconds in one year,12!exceeds the number in 12 years, and 13!surpasses the number of seconds in a century.1.2 PermutationsIf we make use of the factorial notation, the answer in Example 1.9 can be expressed in the following more compact form:5 . 4 . 3 . 2 . 1 10!10 . 9 . 8 . 7 . 6 . 10 . 9 . 8 . 7 . 6 . . .5 . 4 . 3 . 2 . 15!De.nition1.2Given a collection of ndistinct objects, any (linear) arrangement of these objects is called a permutation of the collection.Starting with the letters a, b, c, there are six ways to arrange, or permute, all of the letters: abc, acb, bac, bca, cab, cba. If we are interested in arranging only two of the letters at a time, there are six such size-2 permutations: ab, ba, ac, ca, bc, cb.If there are ndistinct objects and ris an integer, with 1 ≤r≤n, then by the rule of product, the number of permutations of size rfor the nobjects isP(n,r).n.(n.1).(n.2).•••.(n.r+1)1st 2nd 3rd r thposition position position position(n.r)(n.r.1)•••(3)(2)(1)(n)(n.1)(n.2)•••(n.r+1).(n.r)(n.r.1)•••(3)(2)(1)n!(n.r)!For r.0, P(n,0).1 .n!/(n.0)!,so P(n,r).n!/(n.r)!holds for all 0 ≤r≤n. A special case of this result is Example 1.9, where n.10, r.5, and P(10,5).30,240. Whenpermutingallofthe nobjectsinthecollection,wehave r.nand.ndthat P(n,n).n!/0!.n!.Note, for example, that if n≥2, then P(n,2).n!/(n.2)!.n(n.1). When n>3 one .nds that P(n,n.3).n!/[n.(n.3)]!.n!/3!.(n)(n.1)(n.2)•••(5)(4).The number of permutations of size r, where 0 ≤r≤n, from a collection of nobjects, is P(n,r).n!/(n.r)!. (Remember that P(n,r)counts (linear) arrangements in which the objects cannot be repeated.) However, if repetitions are allowed, then by the rule of product there are npossible arrangements, with r≥0.The number of permutations of the letters in the word COMPUTER is 8!. If only .ve of the letters are used, the number of permutations (of size 5) is P(8,5).8!/(8 .5)!.8!/3!.6720. If repetitions of letters are allowed, the number of possible 12-letter sequences is 812 . . 6.872 .1010..EXAMPLE 1.10EXAMPLE 1.11Unlike Example 1.10, the number of (linear) arrangements of the four letters in BALL is 12, not 4!(.24). The reason is that we do not have four distinct letters to arrange. To get the 12 arrangements, we can list them as in Table 1.1(a).The symbol “ .” is read “is approximately equal to.”Chapter 1 Fundamental Principles of CountingTable1.1ABL L A B L1 L2 A B L2 L1AL BL A L1 B L2 A L2 B L1A L L B A L1 L2 B A L2 L1 BBA L L B A L1 L2 B A L2 L1B L A L B L1 A L2 B L2 A L1B L L A B L1 L2 A B L2 L1 AL A B L L1 A B L2 L2 A B L1L A L B L1 A L2 B L2 A L1 BL B A L L1 B A L2 L2 B A L1L B L A L1 B L2 A L2 B L1 AL L A B L1 L2 A B L2 L1 A BL L B A L1 L2 B A L2 L1 B A(a) (b)If the two L’s are distinguished as L1,L2, then we can use our previous ideas on per-mutations of distinct objects; with the four distinct symbols B, A, L1,L2, we have 4!.24 permutations. These are listed in Table 1.1(b). Table 1.1 reveals that for each arrangement in which the L’s are indistinguishable there corresponds a pair of permutations with distinct L’s. Consequently,2 .(Number of arrangements of the letters B, A, L, L). (Number of permutations of the symbols B, A, L1,L2),and the answer to the original problem of .nding all the arrangements of the four letters in BALL is 4!/2 .12.EXAMPLE 1.12Using the idea developed in Example 1.11, we now consider the arrangements of all nine letters in DATABASES.There are 3!.6 arrangements with the A’s distinguished for each arrangement in which the A’s are not distinguished. For example, DA1TA2BA3SES, DA1TA3BA2SES, DA2TA1BA3SES,DA2TA3BA1SES,DA3TA1BA2SES,andDA3TA2BA1SESallcorrespond to DATABASES, when we remove the subscripts on the A’s. In addition, to the arrange-ment DA1TA2BA3SES there corresponds the pair of permutations DA1TA2BA3S1ES2 and DA1TA2BA3S2ES1, when the S’s are distinguished. Consequently,(2!)(3!)(Number of arrangements of the letters in DATABASES). (Number of permutations of the symbols D, A1,T, A2,B, A3,S1,E,S2),so the number of arrangements of the nine letters in DATABASES is 9!/(2!3!).30,240.Beforestatingageneralprincipleforarrangementswithrepeatedsymbols,notethatinour prior two examples we solved a new type of problem by relating it to previous enumeration principles. This practice is common in mathematics in general, and often occurs in the derivations of discrete and combinatorial formulas.

编辑推荐

《离散及组合数学(第5版英文影印版)》由Ralph P. Grimaldi著，主要内容是：The major purpose of this new edition is to continue to provide an introductory survey in both discrete and combinatorial mathematics. The coverage is intended for the beginning student, so there are a great number of examples with detailed explanations. (The examples are numbered separately and a thick line is used to denote the end of each example.) In addition, wherever proofs are given, they too are presented with sufficient detail (with the novice in mind).