Discrete and Combinatorial Mathematics : An Applied Introduction

by Grimaldi, Ralph P.

• ISBN13: 9780201199123
• ISBN10: 0201199122
• Edition: 4th
• Format: Hardcover
• Copyright: 1998-10-01
• Publisher: ADDISON WESLEY LONGMAN INC

Summary

This fourth edition continues to improve on the features that have made it the market leader. The text offers a flexible organization, enabling instructors to adapt the book to their particular courses: discrete mathematics, graph theory, modern algebra, and/or combinatorics. More elementary problems were added, creating a greater variety of level in problem sets, which allows students to perfect skills as they practice. This new edition continues to feature numerous computer science applications-making this the ideal text for preparing students for advanced study.

Table of Contents

PART 1 Fundamentals of Discrete Mathematics	1	(358)
1 Fundamental Principles of Counting	3	(44)
1.1 The Rules of Sum and Product	3	(3)
1.2 Permutations	6	(9)
1.3 Combinations: The Binomial Theorem	15	(12)
1.4 Combinations with Repetition	27	(9)
1.5 An Application in the Physical Sciences (Optional)	36	(1)
1.6 The Catalan Numbers (Optional)	36	(5)
1.7 Summary and Historical Review	41	(6)
2 Fundamentals of Logic	47	(80)
2.1 Basic Connectives and Truth Tables	47	(9)
2.2 Logical Equivalence: The Laws of Logic	56	(12)
2.3 Logical Implication: Rules of Inference	68	(21)
2.4 The Use of Quantifiers	89	(18)
2.5 Quantifiers, Definitions, and the Proofs of Theorems	107	(16)
2.6 Summary and Historical Review	123	(4)
3 Set Theory	127	(36)
3.1 Sets and Subsets	127	(12)
3.2 Set Operations and the Laws of Set Theory	139	(12)
3.3 Counting and Venn Diagrams	151	(3)
3.4 A Word on Probability	154	(3)
3.5 Summary and Historical Review	157	(6)
4 Properties of the Integers: Mathematical Induction	163	(54)
4.1 The Well-Ordering Principle: Mathematical Induction	163	(15)
4.2 Recursive Definitions	178	(11)
4.3 The Division Algorithm: Prime Numbers	189	(11)
4.4 The Greatest Common Divisor: The Euclidean Algorithm	200	(7)
4.5 The Fundamental Theorem of Arithmetic	207	(5)
4.6 Summary and Historical Review	212	(5)
5 Relations and Functions	217	(64)
5.1 Cartesian Products and Relations	218	(4)
5.2 Functions: Plain and One-to-One	222	(8)
5.3 Onto Functions: Stirling Numbers of the Second Kind	230	(8)
5.4 Special Functions	238	(6)
5.5 The Pigeonhole Principle	244	(5)
5.6 Function Composition and Inverse Functions	249	(12)
5.7 Computational Complexity	261	(5)
5.8 Analysis of Algorithms	266	(7)
5.9 Summary and Historical Review	273	(8)
6 Languages: Finite State Machines	281	(30)
6.1 Language: The Set Theory of Strings	282	(10)
6.2 Finite State Machines: A First Encounter	292	(7)
6.3 Finite State Machines: A Second Encounter	299	(7)
6.4 Summary and Historical Review	306	(5)
7 Relations: The Second Time Around	311	(48)
7.1 Relations Revisited: Properties of Relations	311	(8)
7.2 Computer Recognition: Zero-One Matrices and Directed Graphs	319	(12)
7.3 Partial Orders: Hasse Diagrams	331	(10)
7.4 Equivalence Relations and Partitions	341	(5)
7.5 Finite State Machines: The Minimization Process	346	(6)
7.6 Summary and Historical Review	352	(7)
PART 2 Further Topics in Enumeration	359	(116)
8 The Principle of Inclusion and Exclusion	361	(26)
8.1 The Principle of Inclusion and Exclusion	361	(8)
8.2 Generalizations of the Principle	369	(5)
8.3 Derangements: Nothing Is in Its Right Place	374	(2)
8.4 Rook Polynomials	376	(3)
8.5 Arrangements with Forbidden Positions	379	(4)
8.6 Summary and Historical Review	383	(4)
9 Generating Functions	387	(28)
9.1 Introductory Examples	387	(3)
9.2 Definition and Examples: Calculational Techniques	390	(10)
9.3 Partitions of Integers	400	(3)
9.4 The Exponential Generating Function	403	(5)
9.5 The Summation Operator	408	(1)
9.6 Summary and Historical Review	409	(6)
10 Recurrence Relations	415	(60)
10.1 The First-Order Linear Recurrence Relation	415	(9)
10.2 The Second-Order Linear Homogeneous Recurrence Relation with Constant Coefficients	424	(10)
10.3 The Nonhomogeneous Recurrence Relation	434	(11)
10.4 The Method of Generating Functions	445	(5)
10.5 A Special Kind of Nonlinear Recurrence Relation (Optional)	450	(10)
10.6 Divide-and-Conquer Algorithms (Optional)	460	(9)
10.7 Summary and Historical Review	469	(6)
PART 3 Graph Theory and Applications	475	(156)
11 An Introduction to Graph Theory	477	(70)
11.1 Definitions and Examples	477	(8)
11.2 Subgraphs, Complements, and Graph Isomorphism	485	(10)
11.3 Vertex Degree: Euler Trails and Circuits	495	(10)
11.4 Planar Graphs	505	(18)
11.5 Hamilton Paths and Cycles	523	(9)
11.6 Graph Coloring and Chromatic Polynomials	532	(8)
11.7 Summary and Historical Review	540	(7)
12 Trees	547	(44)
12.1 Definitions, Properties, and Examples	547	(6)
12.2 Rooted Trees	553	(17)
12.3 Trees and Sorting	570	(5)
12.4 Weighted Trees and Prefix Codes	575	(5)
12.5 Biconnected Components and Articulation Points	580	(5)
12.6 Summary and Historical Review	585	(6)
13 Optimization and Matching	591	(40)
13.1 Dijkstra's Shortest-Path Algorithm	591	(8)
13.2 Minimal Spanning Trees: The Algorithms of Kruskal and Prim	599	(6)
13.3 Transport Networks: The Max-Flow Min-Cut Theorem	605	(11)
13.4 Matching Theory	616	(9)
13.5 Summary and Historical Review	625	(6)
PART 4 Modern Applied Algebra	631
14 Rings and Modular Arithmetic	633	(30)
14.1 The Ring Structure: Definition and Examples	633	(6)
14.2 Ring Properties and Substructures	639	(7)
14.3 The Integers Modulo n	646	(6)
14.4 Ring Homomorphisms and Isomorphisms	652	(5)
14.5 Summary and Historical Review	657	(6)
15 Boolean Algebra and Switching Functions	663	(38)
15.1 Switching Functions: Disjunctive and Conjunctive Normal Forms	663	(9)
15.2 Gating Networks: Minimal Sums of Products: Karnaugh Maps	672	(10)
15.3 Further Applications: Don't-Care Conditions	682	(5)
15.4 The Structure of a Boolean Algebra (Optional)	687	(9)
15.5 Summary and Historical Review	696	(5)
16 Groups, Coding Theory, and Polya's Method of Enumeration	701	(54)
16.1 Definition, Examples, and Elementary Properties	701	(7)
16.2 Homomorphisms, Isomorphisms, and Cyclic Groups	708	(5)
16.3 Cosets and Lagrange's Theorem	713	(2)
16.4 Elements of Coding Theory	715	(5)
16.5 The Hamming Metric	720	(2)
16.6 The Parity-Check and Generator Matrices	722	(5)
16.7 Group Codes: Decoding with Coset Leaders	727	(4)
16.8 Hamming Matrices	731	(2)
16.9 Counting and Equivalence: Burnside's Theorem	733	(7)
16.10 The Cycle Index	740	(4)
16.11 The Pattern Inventory: Polya's Method of Enumeration	744	(5)
16.12 Summary and Historical Review	749	(6)
17 Finite Fields and Combinatorial Designs	755
17.1 Polynomial Rings	755	(8)
17.2 Irreducible Polynomials: Finite Fields	763	(9)
17.3 Latin Squares	772	(6)
17.4 Finite Geometries and Affine Planes	778	(5)
17.5 Block Designs and Projective Planes	783	(5)
17.6 Summary and Historical Review	788
Appendix 1 Exponential and Logarithmic Functions	A-1	(10)
Appendix 2 Matrices, Matrix Operations, and Determinants	A-11	(14)
Appendix 3 Countable and Uncountable Sets	A-25
Solutions	S-1
Index	I-1