Discrete and Combinatorial Mathematics (Classic Version)

<p> PART 1. FUNDAMENTALS OF DISCRETE MATHEMATICS. </p> <div style="margin-left: 0.2in;"> 1. Fundamental Principles of Counting. </div> <br> <p> </p> <div style="margin-left: 0.4in;"> The Rules of Sum and Product. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Permutations. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Combinations: The Binomial Theorem. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Combinations with Repetition. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> The Catalan Numbers (Optional). </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Summary and Historical Review. </div> <p></p> <div style="margin-left: 0.2in;"> 2. Fundamentals of Logic. </div> <br> <p> </p> <div style="margin-left: 0.4in;"> Basic Connectives and Truth Tables. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Logical Equivalence: The Laws of Logic. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Logical Implication: Rules of Inference. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> The Use of Quantifiers. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Quantifiers, Definitions, and the Proofs of Theorems. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Summary and Historical Review. </div> <p></p> <div style="margin-left: 0.2in;"> 3. Set Theory. </div> <br> <p> </p> <div style="margin-left: 0.4in;"> Sets and Subsets. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Set Operations and the Laws of Set Theory. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Counting and Venn Diagrams. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> A First Word on Probability. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> The Axioms of Probability (Optional). </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Conditional Probability: Independence (Optional). </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Discrete Random Variables (Optional). </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Summary and Historical Review. </div> <p></p> <div style="margin-left: 0.2in;"> 4. Properties of the Integers: Mathematical Induction. </div> <br> <p> </p> <div style="margin-left: 0.4in;"> The Well-Ordering Principle: Mathematical Induction. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Recursive Definitions. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> The Division Algorithm: Prime Numbers. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> The Greatest Common Divisor: The Euclidean Algorithm. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> The Fundamental Theorem of Arithmetic. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Summary and Historical Review. </div> <p></p> <div style="margin-left: 0.2in;"> 5. Relations and Functions. </div> <br> <p> </p> <div style="margin-left: 0.4in;"> Cartesian Products and Relations. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Functions: Plain and One-to-One. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Onto Functions: Stirling Numbers of the Second Kind. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Special Functions. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> The Pigeonhole Principle. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Function Composition and Inverse Functions. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Computational Complexity. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Analysis of Algorithms. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Summary and Historical Review. </div> <p></p> <div style="margin-left: 0.2in;"> 6. Languages: Finite State Machines. </div> <br> <p> </p> <div style="margin-left: 0.4in;"> Language: The Set Theory of Strings. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Finite State Machines: A First Encounter. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Finite State Machines: A Second Encounter. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Summary and Historical Review. </div> <p></p> <div style="margin-left: 0.2in;"> 7. Relations: The Second Time Around. </div> <br> <p> </p> <div style="margin-left: 0.4in;"> Relations Revisited: Properties of Relations. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Computer Recognition: Zero-One Matrices and Directed Graphs. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Partial Orders: Hasse Diagrams. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Equivalence Relations and Partitions. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Finite State Machines: The Minimization Process. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Summary and Historical Review. </div> <p></p> <p> PART 2. FURTHER TOPICS IN ENUMERATION. </p> <div style="margin-left: 0.2in;"> 8. The Principle of Inclusion and Exclusion. </div> <br> <p> </p> <div style="margin-left: 0.4in;"> The Principle of Inclusion and Exclusion. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Generalizations of the Principle. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Derangements: Nothing Is in Its Right Place. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Rook Polynomials. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Arrangements with Forbidden Positions. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Summary and Historical Review. </div> <p></p> <div style="margin-left: 0.2in;"> 9. Generating Functions. </div> <br> <p> </p> <div style="margin-left: 0.4in;"> Introductory Examples. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Definition and Examples: Calculational Techniques. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Partitions of Integers. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> The Exponential Generating Functions. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> The Summation Operator. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Summary and Historical Review. </div> <p></p> <div style="margin-left: 0.2in;"> 10. Recurrence Relations. </div> <br> <p> </p> <div style="margin-left: 0.4in;"> The First-Order Linear Recurrence Relation. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> The Second-Order Linear Homogeneous Recurrence Relation with Constant Coefficients. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> The Nonhomogeneous Recurrence Relation. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> The Method of Generating Functions. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> A Special Kind of Nonlinear Recurrence Relation (Optional). </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Divide and Conquer Algorithms. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Summary and Historical Review. </div> <p></p> <p> PART 3. GRAPH THEORY AND APPLICATIONS. </p> <div style="margin-left: 0.2in;"> 11. An Introduction to Graph Theory. </div> <br> <p> </p> <div style="margin-left: 0.4in;"> Definitions and Examples. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Subgraphs, Complements, and Graph Isomorphism. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Vertex Degree: Euler Trails and Circuits. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Planar Graphs. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Hamilton Paths and Cycles. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Graph Coloring and Chromatic Polynomials. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Summary and Historical Review. </div> <p></p> <div style="margin-left: 0.2in;"> 12. Trees. </div> <br> <p> </p> <div style="margin-left: 0.4in;"> Definitions, Properties, and Examples. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Rooted Trees. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Trees and Sorting. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Weighted Trees and Prefix Codes. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Biconnected Components and Articulation Points. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Summary and Historical Review. </div> <p></p> <div style="margin-left: 0.2in;"> 13. Optimization and Matching. </div> <br> <p> </p> <div style="margin-left: 0.4in;"> Dijkstra's Shortest Path Algorithm. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Minimal Spanning Trees: The Algorithms of Kruskal and Prim. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Transport Networks: The Max-Flow Min-Cut Theorem. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Matching Theory. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Summary and Historical Review. </div> <p></p> <p> PART 4. MODERN APPLIED ALGEBRA. </p> <div style="margin-left: 0.2in;"> 14. Rings and Modular Arithmetic. </div> <br> <p> </p> <div style="margin-left: 0.4in;"> The Ring Structure: Definition and Examples. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Ring Properties and Substructures. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> The Integers Modulo n. Cryptology. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Ring Homomorphisms and Isomorphisms: The Chinese Remainder Theorem. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Summary and Historical Review. </div> <p></p> <div style="margin-left: 0.2in;"> 15. Boolean Algebra and Switching Functions. </div> <br> <p> </p> <div style="margin-left: 0.4in;"> Switching Functions: Disjunctive and Conjunctive Normal Forms. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Gating Networks: Minimal Sums of Products: Karnaugh Maps. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Further Applications: Don't-Care Conditions. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> The Structure of a Boolean Algebra (Optional). </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Summary and Historical Review. </div> <p></p> <div style="margin-left: 0.2in;"> 16. Groups, Coding Theory, and Polya's Theory of Enumeration. </div> <br> <p> </p> <div style="margin-left: 0.4in;"> Definition, Examples, and Elementary Properties. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Homomorphisms, Isomorphisms, and Cyclic Groups. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Cosets and Lagrange's Theorem. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> The RSA Cipher (Optional). </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Elements of Coding Theory. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> The Hamming Metric. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> The Parity-Check and Generator Matrices. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Group Codes: Decoding with Coset Leaders. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Hamming Matrices. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Counting and Equivalence: Burnside's Theorem. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> The Cycle Index. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> The Pattern Inventory: Polya's Method of Enumeration. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Summary and Historical Review. </div> <p></p> <div style="margin-left: 0.2in;"> 17. Finite Fields and Combinatorial Designs. </div> <br> <p> </p> <div style="margin-left: 0.4in;"> Polynomial Rings. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Irreducible Polynomials: Finite Fields. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Latin Squares. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Finite Geometries and Affine Planes. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Block Designs and Projective Planes. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Summary and Historical Review. </div> <p></p> <div style="margin-left: 0.2in;"> Appendices. </div> <br> <p> </p> <div style="margin-left: 0.4in;"> Exponential and Logarithmic Functions. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Matrices, Matrix Operations, and Determinants. </div> <p></p> <p> </p> <div style="margin-left: 0.4in;"> Countable and Uncountable Sets. </div> <p></p> <div style="margin-left: 0.2in;"> Solutions. </div> <br> <div style="margin-left: 0.2in;"> Index. </div> <br>