Discrete and Combinatorial Mathematics (Classic Version), 5th edition

I. FUNDAMENTALS OF DISCRETE MATHEMATICS

• 1. Fundamental Principles of Counting
  • The Rules of Sum and Product
  • Permutations
  • Combinations: The Binomial Theorem
  • Combinations with Repetition
  • The Catalan Numbers (Optional)
  • Summary and Historical Review
• 2. Fundamentals of Logic
  • Basic Connectives and Truth Tables
  • Logical Equivalence: The Laws of Logic
  • Logical Implication: Rules of Inference
  • The Use of Quantifiers
  • Quantifiers, Definitions, and the Proofs of Theorems
  • Summary and Historical Review
• 3. Set Theory
  • Sets and Subsets
  • Set Operations and the Laws of Set Theory
  • Counting and Venn Diagrams
  • A First Word on Probability
  • The Axioms of Probability (Optional)
  • Conditional Probability: Independence (Optional)
  • Discrete Random Variables (Optional)
  • Summary and Historical Review
• 4. Properties of the Integers: Mathematical Induction
  • The Well-Ordering Principle: Mathematical Induction
  • Recursive Definitions
  • The Division Algorithm: Prime Numbers
  • The Greatest Common Divisor: The Euclidean Algorithm
  • The Fundamental Theorem of Arithmetic
  • Summary and Historical Review
• 5. Relations and Functions
  • Cartesian Products and Relations
  • Functions: Plain and One-to-One
  • Onto Functions: Stirling Numbers of the Second Kind
  • Special Functions
  • The Pigeonhole Principle
  • Function Composition and Inverse Functions
  • Computational Complexity
  • Analysis of Algorithms
  • Summary and Historical Review
• 6. Languages: Finite State Machines
  • Language: The Set Theory of Strings
  • Finite State Machines: A First Encounter
  • Finite State Machines: A Second Encounter
  • Summary and Historical Review
• 7. Relations: The Second Time Around
  • Relations Revisited: Properties of Relations
  • Computer Recognition: Zero-One Matrices and Directed Graphs
  • Partial Orders: Hasse Diagrams
  • Equivalence Relations and Partitions
  • Finite State Machines: The Minimization Process
  • Summary and Historical Review

II. FURTHER TOPICS IN ENUMERATION

• 8. The Principle of Inclusion and Exclusion
  • Derangements: Nothing Is in Its Right Place
  • Rook Polynomials
  • Arrangements with Forbidden Positions
  • Summary and Historical Review
• 9. Generating Functions
  • Introductory Examples
  • Definition and Examples: Calculational Techniques
  • Partitions of Integers
  • The Exponential Generating Functions
  • The Summation Operator
  • Summary and Historical Review
• 10. Recurrence Relations
  • The First-Order Linear Recurrence Relation
  • The Second-Order Linear Homogeneous Recurrence Relation with Constant Coefficients
  • The Nonhomogeneous Recurrence Relation
  • The Method of Generating Functions
  • A Special Kind of Nonlinear Recurrence Relation (Optional)
  • Divide and Conquer Algorithms
  • Summary and Historical Review

III. GRAPH THEORY AND APPLICATIONS

• 11. An Introduction to Graph Theory
  • Definitions and Examples
  • Subgraphs, Complements, and Graph Isomorphism
  • Vertex Degree: Euler Trails and Circuits
  • Planar Graphs
  • Hamilton Paths and Cycles
  • Graph Coloring and Chromatic Polynomials
  • Summary and Historical Review
• 12. Trees
  • Definitions, Properties, and Examples
  • Rooted Trees
  • Trees and Sorting
  • Weighted Trees and Prefix Codes
  • Biconnected Components and Articulation Points
  • Summary and Historical Review
• 13. Optimization and Matching
  • Dijkstra's Shortest Path Algorithm
  • Minimal Spanning Trees: The Algorithms of Kruskal and Prim
  • Transport Networks: The Max-Flow Min-Cut Theorem
  • Matching Theory
  • Summary and Historical Review

IV. MODERN APPLIED ALGEBRA

• 14. Rings and Modular Arithmetic
  • The Ring Structure: Definition and Examples
  • Ring Properties and Substructures
  • The Integers Modulo n. Cryptology
  • Ring Homomorphisms and Isomorphisms: The Chinese Remainder Theorem
  • Summary and Historical Review
• 15. Boolean Algebra and Switching Functions
  • Switching Functions: Disjunctive and Conjunctive Normal Forms
  • Gating Networks: Minimal Sums of Products: Karnaugh Maps
  • Further Applications: Don't-Care Conditions
  • The Structure of a Boolean Algebra (Optional)
  • Summary and Historical Review.
• 16. Groups, Coding Theory, and Polya's Theory of Enumeration
  • Definition, Examples, and Elementary Properties
  • Homomorphisms, Isomorphisms, and Cyclic Groups
  • Cosets and Lagrange's Theorem
  • The RSA Cipher (Optional)
  • Elements of Coding Theory
  • The Hamming Metric
  • The Parity-Check and Generator Matrices
  • Group Codes: Decoding with Coset Leaders
  • Hamming Matrices
  • Counting and Equivalence: Burnside's Theorem
  • The Cycle Index
  • The Pattern Inventory: Polya's Method of Enumeration
  • Summary and Historical Review
• 17. Finite Fields and Combinatorial Designs
  • Polynomial Rings
  • Irreducible Polynomials: Finite Fields
  • Latin Squares
  • Finite Geometries and Affine Planes
  • Block Designs and Projective Planes
  • Summary and Historical Review

Appendices

• Exponential and Logarithmic Functions
• Matrices, Matrix Operations, and Determinants
• Countable and Uncountable Sets
• Solutions
• Index