Discrete Mathematics: An Introduction to Proofs and Combinatorics

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.

DISCRETE MATHEMATICS, INTERNATIONAL EDITION combines a balance of theory and applications with mathematical rigor and an accessible writing style. The author uses a range of examples to teach core concepts, while corresponding exercises allow students to apply what they learn. Throughout the text, engaging anecdotes and topics of interest inform as well as motivate learners. The text is ideal for one- or two-semester courses and for students who are typically mathematics, mathematics education, or computer science majors. Part I teaches student how to write proofs; Part II focuses on computation and problem solving. The second half of the book may also be suitable for introductory courses in combinatorics and graph theory.