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 Z and R
Appendix B: Pseudocode
Appendix C: Answers to Selected Exercises
Bibliography
Index