Acknowledgements
Preface
How to use this book
Introduction and Preliminaries
What is Discrete Mathematics?
Mathematical Statements
Atomic and Molecular Statements
Implications
Predicates and Quantifiers
Exercises
Sets
Notation
Relationships Between Sets
Operations On Sets
Venn Diagrams
Exercises
Functions
Describing Functions
Surjections, Injections, and Bijections
Image and Inverse Image
Exercises
Counting
Additive and Multiplicative Principles
Counting With Sets
Principle of Inclusion/Exclusion
Exercises
Binomial Coefficients
Subsets
Bit Strings
Lattice Paths
Binomial Coefficients
Pascal's Triangle
Exercises
Combinations and Permutations
Exercises
Combinatorial Proofs
Patterns in Pascal's Triangle
More Proofs
Exercises
Stars and Bars
Exercises
Advanced Counting Using PIE
Counting Derangements
Counting Functions
Exercises
Chapter Summary
Chapter Review
Sequences
Describing Sequences
Exercises
Arithmetic and Geometric Sequences
Sums of Arithmetic and Geometric Sequences
Exercises
Polynomial Fitting
Exercises
Solving Recurrence Relations
The Characteristic Root Technique
Exercises
Induction
Stamps
Formalizing Proofs
Examples
Strong Induction
Exercises
Chapter Summary
Chapter Review
Symbolic Logic and Proofs
Propositional Logic
Truth Tables
Logical Equivalence
Deductions
Beyond Propositions
Exercises
Proofs
Direct Proof
Proof by Contrapositive
Proof by Contradiction
Proof by (counter) Example
Proof by Cases
Exercises
Chapter Summary
Chapter Review
Graph Theory
Definitions
Exercises
Trees
Properties of Trees
Rooted Trees
Spanning Trees
Exercises
Planar Graphs
Non-planar Graphs
Polyhedra
Exercises
Coloring
Coloring in General
Coloring Edges
Exercises
Euler Paths and Circuits
Hamilton Paths
Exercises
Matching in Bipartite Graphs
Exercises
Chapter Summary
Chapter Review
Additional Topics
Generating Functions
Building Generating Functions
Differencing
Multiplication and Partial Sums
Solving Recurrence Relations with Generating Functions
Exercises
Introduction to Number Theory
Divisibility
Remainder Classes
Properties of Congruence
Solving Congruences
Solving Linear Diophantine Equations
Exercises
Selected Hints
Selected Solutions
List of Symbols
Index