Discrete and Combinatorial Mathematics (Classic Version), Global Edition

Ralph Peter Grimaldi is Professor at Rose-Hulman Institute of Technology, Terre Haute, United States. His research interests include combinatorics, graph theory, discrete mathematics, differential equations, calculus, abstract algebra and linear algebra.

• PART 1. FUNDAMENTALS OF DISCRETE MATHEMATICS Fundamental Principles of Counting The Rules of Sum and ProductPermutationsCombinations: The Binomial TheoremCombinations with RepetitionThe Catalan Numbers (Optional)Summary and Historical Review Fundamentals of Logic Basic Connectives and Truth TablesLogical Equivalence: The Laws of LogicLogical Implication: Rules of InferenceThe Use of QuantifiersQuantifiers, Definitions, and the Proofs of TheoremsSummary and Historical Review Set Theory Sets and SubsetsSet Operations and the Laws of Set TheoryCounting and Venn DiagramsA First Word on ProbabilityThe Axioms of Probability (Optional)Conditional Probability: Independence (Optional)Discrete Random Variables (Optional)Summary and Historical Review Properties of the Integers: Mathematical Induction The Well-Ordering Principle: Mathematical InductionRecursive DefinitionsThe Division Algorithm: Prime NumbersThe Greatest Common Divisor: The Euclidean AlgorithmThe Fundamental Theorem of ArithmeticSummary and Historical Review Relations and Functions Cartesian Products and RelationsFunctions: Plain and One-to-OneOnto Functions: Stirling Numbers of the Second KindSpecial FunctionsThe Pigeonhole PrincipleFunction Composition and Inverse FunctionsComputational ComplexityAnalysis of AlgorithmsSummary and Historical Review Languages: Finite State Machines Language: The Set Theory of StringsFinite State Machines: A First EncounterFinite State Machines: A Second EncounterSummary and Historical Review Relations: The Second Time Around Relations Revisited: Properties of RelationsComputer Recognition: Zero-One Matrices and Directed GraphsPartial Orders: Hasse DiagramsEquivalence Relations and PartitionsFinite State Machines: The Minimization ProcessSummary and Historical Review PART 2. FURTHER TOPICS IN ENUMERATION The Principle of Inclusion and Exclusion The Principle of Inclusion and ExclusionGeneralizations of the PrincipleDerangements: Nothing Is in Its Right PlaceRook PolynomialsArrangements with Forbidden PositionsSummary and Historical Review Generating Functions Introductory ExamplesDefinition and Examples: Calculational TechniquesPartitions of IntegersThe Exponential Generating FunctionsThe Summation OperatorSummary and Historical Review Recurrence Relations The First-Order Linear Recurrence RelationThe Second-Order Linear Homogeneous Recurrence Relation with Constant CoefficientsThe Nonhomogeneous Recurrence RelationThe Method of Generating FunctionsA Special Kind of Nonlinear Recurrence Relation (Optional)Divide and Conquer AlgorithmsSummary and Historical Review PART 3. GRAPH THEORY AND APPLICATIONS An Introduction to Graph Theory Definitions and ExamplesSubgraphs, Complements, and Graph IsomorphismVertex Degree: Euler Trails and CircuitsPlanar GraphsHamilton Paths and CyclesGraph Coloring and Chromatic PolynomialsSummary and Historical Review Trees Definitions, Properties, and ExamplesRooted TreesTrees and SortingWeighted Trees and Prefix CodesBiconnected Components and Articulation PointsSummary and Historical Review Optimization and Matching Dijkstra's Shortest Path AlgorithmMinimal Spanning Trees: The Algorithms of Kruskal and PrimTransport Networks: The Max-Flow Min-Cut TheoremMatching TheorySummary and Historical Review PART 4. MODERN APPLIED ALGEBRA Rings and Modular Arithmetic The Ring Structure: Definition and ExamplesRing Properties and SubstructuresThe Integers Modulo n. CryptologyRing Homomorphisms and Isomorphisms: The Chinese Remainder TheoremSummary and Historical Review Boolean Algebra and Switching Functions Switching Functions: Disjunctive and Conjunctive Normal FormsGating Networks: Minimal Sums of Products: Karnaugh MapsFurther Applications: Don't-Care ConditionsThe Structure of a Boolean Algebra (Optional)Summary and Historical Review Groups, Coding Theory, and Polya's Theory of Enumeration Definition, Examples, and Elementary PropertiesHomomorphisms, Isomorphisms, and Cyclic GroupsCosets and Lagrange's TheoremThe RSA Cipher (Optional)Elements of Coding TheoryThe Hamming MetricThe Parity-Check and Generator MatricesGroup Codes: Decoding with Coset LeadersHamming MatricesCounting and Equivalence: Burnside's TheoremThe Cycle IndexThe Pattern Inventory: Polya's Method of EnumerationSummary and Historical Review Finite Fields and Combinatorial Designs Polynomial RingsIrreducible Polynomials: Finite FieldsLatin SquaresFinite Geometries and Affine PlanesBlock Designs and Projective PlanesSummary and Historical Review Appendices Exponential and Logarithmic FunctionsMatrices, Matrix Operations, and DeterminantsCountable and Uncountable Sets SolutionsIndex