Discrete and Combinatorial Mathematics: An Applied Introduction

*Appropriate for four different courses: Discrete Mathematics; Combinatorics; Graph Theory; Modern Applied Algebra. *Flexible, modular organization. *This text has an enhanced mathematical approach, with carefully thought out examples, including many examples with computer sciences applications. *Carefully thought-out examples, including examples with computer science applications. Students can learn by reading the text. *The Fourth Edition has added more elementary problems, creating a larger variety of level within the problem sets which allows students to establish skills as they practice. *Chapter summaries allow the student to review what they have learned, while historical reviews and biographies bring a human element to their assignments. 1. Fundamentals of Discrete Mathematics. Fundamental Principles of Counting. The Rules of Sum and Product. Permutations. Combinations:. The Binomial Theorem. Combinations with Repetition: Distributions. An Application in the Physical Sciences (Optional). 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. 3. Set Theory. Sets and Subsets. Set Operations and the Laws of Set Theory. Counting and Venn Diagrams. A Word on Probability. 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. 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. 6. Languages: Finite State Machines. Language: The Set Theory of Strings. Finite State Machines: A First Encounter. Finite State Machines: A Second Encounter. 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. 7. Further Topics in Enumeration. The Principle of Inclusion and Exclusion. Generalizations of the Principle (Optional). Derangements: Nothing Is in Its Right Place. Rook Polynomials. Arrangements with Forbidden Positions. 8. Generating Functions. Introductory Examples. Definition and Examples: Calculational Techniques. Partitions of Integers. Exponential Generating Functions. The Summation Operator. 9. Recurrence Relations. The First-Order Linear Recurrence Relation. The Second-Order Linear 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 (Optional). 10. Graph Theory and Applications. 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. 11. Trees. Definitions, Properties, and Examples. Rooted Trees. Trees and Sorting Algorithms. Weighted Trees and Prefix Codes. Biconnected Components and Articulation Points. 12. Optimization and Matching. Dijkstras Shortest Path Algorithm. Minimal Spanning Trees. Transport Networks: The Max-Flow Min-Cut Theorem. Matching Theory. 13. Modern Applied Algebra. Rings and Modular Arithmetic. The Ring Structure: Definition and Examples. Ring Properties and Substructures. The Integers Modulo n. Ring Homomorphisms and Isomorphisms. 14. Boolean Algebra and Switching Functions. Switching Functions: Disjunctive and Conjunctive Normal Forms. Gating Networks: Minimal Sums of Products: Karnaugh Maps. Further Applications: Dont Care Conditions. The Structure of a Boolean Algebra (Optional). 15. Groups, Coding Theory, and Polyas Method of Enumeration. Definition, Examples, and Elementary Properties. Homomorphisms, Isomorphisms, and Cyclic Groups. Cosets and Lagranges Theorem. Elements of Coding Theory. The Hamming Metric. The Parity-Check and Generator trices. Group Codes: Decoding with Coset Leaders. Hamming Matrices. Counting and Equivalence: Burnsides Theorem. The Cycle Index. The Pattern Inventory: Polyas Method of Enumeration. 16. Finite Fields and Combinatorial Designs. Polynomial Rings. Irreducible Polynomials: Finite Fields. Latin Squares. Finite Geometries and Affine Planes. Block Designs and Projective Planes. Appendices. Exponential and Logarithmic Functions. Matrices, Matrix Operations, and Determinants. Countable and Uncountable Sets. Solutions. Index.

Table of Contents:
1. Fundamentals of Discrete Mathematics. Fundamental Principles of Counting. The Rules of Sum and Product. Permutations. Combinations:. The Binomial Theorem. Combinations with Repetition: Distributions. An Application in the Physical Sciences (Optional). 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. 3. Set Theory. Sets and Subsets. Set Operations and the Laws of Set Theory. Counting and Venn Diagrams. A Word on Probability. 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. 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. 6. Languages: Finite State Machines. Language: The Set Theory of Strings. Finite State Machines: A First Encounter. Finite State Machines: A Second Encounter. 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. 7. Further Topics in Enumeration. The Principle of Inclusion and Exclusion. Generalizations of the Principle (Optional). Derangements: Nothing Is in Its Right Place. Rook Polynomials. Arrangements with Forbidden Positions. 8. Generating Functions. Introductory Examples. Definition and Examples: Calculational Techniques. Partitions of Integers. Exponential Generating Functions. The Summation Operator. 9. Recurrence Relations. The First-Order Linear Recurrence Relation. The Second-Order Linear 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 (Optional). 10. Graph Theory and Applications. 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. 11. Trees. Definitions, Properties, and Examples. Rooted Trees. Trees and Sorting Algorithms. Weighted Trees and Prefix Codes. Biconnected Components and Articulation Points. 12. Optimization and Matching. Dijkstras Shortest Path Algorithm. Minimal Spanning Trees. Transport Networks: The Max-Flow Min-Cut Theorem. Matching Theory. 13. Modern Applied Algebra. Rings and Modular Arithmetic. The Ring Structure: Definition and Examples. Ring Properties and Substructures. The Integers Modulo n. Ring Homomorphisms and Isomorphisms. 14. Boolean Algebra and Switching Functions. Switching Functions: Disjunctive and Conjunctive Normal Forms. Gating Networks: Minimal Sums of Products: Karnaugh Maps. Further Applications: Dont Care Conditions. The Structure of a Boolean Algebra (Optional). 15. Groups, Coding Theory, and Polyas Method of Enumeration. Definition, Examples, and Elementary Properties. Homomorphisms, Isomorphisms, and Cyclic Groups. Cosets and Lagranges Theorem. Elements of Coding Theory. The Hamming Metric. The Parity-Check and Generator trices. Group Codes: Decoding with Coset Leaders. Hamming Matrices. Counting and Equivalence: Burnsides Theorem. The Cycle Index. The Pattern Inventory: Polyas Method of Enumeration. 16. Finite Fields and Combinatorial Designs. Polynomial Rings. Irreducible Polynomials: Finite Fields. Latin Squares. Finite Geometries and Affine Planes. Block Designs and Projective Planes. Appendices. Exponential and Logarithmic Functions. Matrices, Matrix Operations, and Determinants. Countable and Uncountable Sets. Solutions. Index.