Discrete Mathematics An Introduction to Proofs and Combinatorics, International Edition

0. Representing Numbers. Part I: PROOFS. 1. Logic and Sets. Statement Forms and Logical Equivalences. Set Notation. Quantifiers. Set Operations and Identities. Valid Arguments. Chapter 1 Review Problems. 2. Basic Proof Writing. Direct Demonstration. General Demonstration (Part 1). General Demonstration (Part 2). Indirect Arguments. Splitting into Cases. Chapter 2 Review Problems. 3. Elementary Number Theory. Divisors. Consequences of Well-Ordering. Euclid's Algorithm and Lemma. Rational Numbers. Irrational Numbers. Modular Arithmetic. Chapter 3 Review Problems. 4. Indexed by Integers. Sequences, Indexing, and Recursion. Sigma Notation. Mathematical Induction, an Introduction. Induction and Summations. Strong Induction. The Binomial Theorem. Chapter 4 Review Problems. 5. Relations. General Relations. Special Relations on Sets. Basics of Functions. Special Functions. General Set Constructions. Cardinality. Chapter 5 Review Problems. Part II: COMBINATORICS. 6. Basic Counting. The Multiplication Principle. Permutations and Combinations. Addition and Subtraction. Probability. Applications of Combinations. Correcting for Overcounting. Chapter 6 Review Problems. 7. More Counting. Inclusion-Exclusion. Multinomial Coefficients. Generating Functions. Counting Orbits. Combinatorial Arguments. Chapter 7 Review Problems. 8. Basic Graph Theory. Motivation and Introduction. Matrices and Special Graphs. Isomorphisms. Invariants. Directed Graphs and Markov Chains. Chapter 8 Review Problems. 9. Graph Properties. Connectivity. Euler Circuits. Hamiltonian Cycles. Planar Graphs. Chromatic Number. Chapter 9 Review Problems. 10. Trees and Algorithms. Trees. Search Trees. Weighted Trees. Analysis of Algorithms (Part 1). Analysis of Algorithms (Part 2). Chapter 10 Review Problems. Appendix A: Assumed Properties of Z and R. Appendix B: Pseudocode.