Discrete Mathematics and Applications

Cover
Half Title
Title
Copyright
Dedication
Contents
Preface
Acknowledgments
Introduction: Representing Numbers
I: Proofs
   1: Logic and Sets
      1.1: Statement forms and logical equivalences
         1.1.1: Statement forms
         1.1.2: Logical equivalences
         1.1.3: Digital circuits
      1.2: Set notation
         1.2.1: Paradoxes
         1.2.2: Software implementation of sets
      1.3: Quantifiers
         1.3.1: Negating quantified statements
      1.4: Set operations and identities
         1.4.1: Software implementation of set operations
      1.5: Valid arguments
         1.5.1: Arguments involving quantifiers
      1.6: Review problems
   2: Basic Proof Writing
      2.1: Direct demonstration
         2.1.1: Existential statements
         2.1.2: Counterexamples
         2.1.3: Universal statements for small universes
      2.2: General demonstration (Part 1)
         2.2.1: If-then statements
         2.2.2: Subsets
         2.2.3: Set equalities
      2.3: General demonstration (Part 2)
         2.3.1: If and only if statements
         2.3.2: Set equalities revisited
         2.3.3: Sets with particular forms
      2.4: Indirect arguments
         2.4.1: Proofs by contradiction
         2.4.2: Proving the contrapositive
      2.5: Splitting into cases
      2.6: Review problems
   3: Elementary Number Theory
      3.1: Divisors
         3.1.1: Parity
         3.1.2: Divisibility
         3.1.3: Primes
         3.1.4: GCD’s
      3.2: Well-ordering, division, and codes
         3.2.1: Computer searches for large primes
         3.2.2: Integer division
         3.2.3: Rounding numbers
         3.2.4: Applications of mod
      3.3: Euclid’s Algorithm and Lemma
         3.3.1: Euclid’s Algorithm
         3.3.2: Lemmas on factoring
      3.4: Rational and irrational numbers
         3.4.1: Rational numbers
         3.4.2: Irrational numbers
      3.5: Modular arithmetic and encryption
         3.5.1: Linear ciphers
         3.5.2: RSA encryption
         3.5.3: Primality conditions
         3.5.4: The additive group of integers modulo n
      3.6: Review problems
   4: Indexed by Integers
      4.1: Sequences, indexing, and recursion
         4.1.1: Factorials and binomial coefficients
         4.1.2: Sequences
         4.1.3: Two special kinds of sequences
         4.1.4: Reindexing a sequence
         4.1.5: Recursion
         4.1.6: Software implementation of recursion
      4.2: Sigma notation
         4.2.1: Product notation
         4.2.2: General summation formulas
      4.3: Mathematical induction: An introduction
      4.4: Induction and summations
      4.5: Strong induction
         4.5.1: Standard factorization
         4.5.2: The Fibonacci numbers
      4.6: The Binomial Theorem
      4.7: Review problems
   5: Relations
      5.1: General relations
         5.1.1: Databases
         5.1.2: Representing relations
         5.1.3: Properties of relations on sets
      5.2: Special relations on sets
         5.2.1: Order relations
         5.2.2: Equivalence relations
         5.2.3: Partitions
      5.3: Basics of functions
         5.3.1: Composing functions
         5.3.2: Focusing on real functions
      5.4: Special functions
         5.4.1: One-to-one and onto functions
         5.4.2: Inverse functions
         5.4.3: Logarithms
      5.5: General set constructions
         5.5.1: Images and inverse images
         5.5.2: Indexed set operations
      5.6: Cardinality
      5.7: Review problems
II: Combinatorics
   6: Basic Counting
      6.1: The multiplication principle
      6.2: Permutations and combinations
         6.2.1: Permutations
         6.2.2: Combinations
         6.2.3: Permutations vs. combinations
         6.2.4: The proof of Theorem 6.4
      6.3: Addition and subtraction
         6.3.1: Disjoint events
         6.3.2: Complements
         6.3.3: Basic inclusion and exclusion
      6.4: Probability
         6.4.1: Conditional probability
      6.5: Applications of combinations
         6.5.1: Paths in a grid
         6.5.2: Poker
         6.5.3: Choices with repetition
      6.6: Correcting for overcounting
      6.7: Review problems
   7: More Counting
      7.1: Inclusion–exclusion
         7.1.1: Derangements
      7.2: Multinomial coefficients
      7.3: Generating functions
         7.3.1: The algebra
         7.3.2: The combinatorics
         7.3.3: More algebra
         7.3.4: More combinatorics
      7.4: Counting orbits
         7.4.1: The delayed proofs
      7.5: Combinatorial arguments
      7.6: Review problems
   8: Basic Graph Theory
      8.1: Motivation and introduction
         8.1.1: Motivation
         8.1.2: Introduction
         8.1.3: Parts of a graph
      8.2: Special graphs
      8.3: Matrices
      8.4: Isomorphisms
      8.5: Invariants
         8.5.1: Graph operations
      8.6: Directed graphs and Markov chains
         8.6.1: Markov chains
      8.7: Review problems
   9: Graph Properties
      9.1: Connectivity
         9.1.1: Edge connectivity
      9.2: Euler circuits
      9.3: Hamiltonian cycles
      9.4: Planar graphs
         9.4.1: Crossing number
      9.5: Chromatic number
         9.5.1: Coloring maps
      9.6: Review problems
   10: Trees and Algorithms
      10.1: Trees
      10.2: Search trees
         10.2.1: Breadth-first search trees
         10.2.2: Depth-first search trees
         10.2.3: Applications
      10.3: Weighted trees
         10.3.1: Minimum spanning trees
         10.3.2: Shortest path trees
      10.4: Analysis of algorithms (Part 1)
         10.4.1: Search algorithms
         10.4.2: Complexity of algorithms
         10.4.3: Growth of functions
         10.4.4: Order of algorithms
      10.5: Analysis of algorithms (Part 2)
         10.5.1: Decision trees
         10.5.2: Sorting algorithms
      10.6: Review problems
Appendix A: Assumed Properties of ℤ and ℝ
Appendix B: Pseudocode
Appendix C: Answers to Selected Exercises
Bibliography
Index