Skip to main content
Discrete Mathematics:
An Open Introduction, 4th edition (preview)
Oscar Levin
Contents
Index
Search Book
close
Search Results:
No results.
Prev
Up
Next
Front Matter
chevron_left
Colophon
Dedication
Acknowledgements
Preface
How to use this book
0
Introduction and Preliminaries
chevron_left
0.1
What is Discrete Mathematics?
chevron_left
0.1
Reading Questions
0.2
Discrete Structures
chevron_left
0.2.1
Introduction
0.2.2
Sets
0.2.3
Functions
0.2.4
Sequences
0.2.5
Relations
0.2.6
Graphs
0.2.7
Even More Structures
1
Logic and Proofs
chevron_left
1.1
Mathematical Statements
chevron_left
1.1.1
Introduction
1.1.1
Preview Activity
1.1.2
Atomic and Molecular Statements
1.1.3
Quantifiers and Predicates
1.1
Reading Questions
1.1
Practice Problems
1.1
Additional Exercises
1.2
Implications
chevron_left
1.2.1
Introduction
1.2.2
Understanding the Truth Table
1.2.3
Related Statements
1.2
Reading Questions
1.2
Practice Problems
1.2
Additional Exercises
1.3
Rules of Logic
chevron_left
1.3.1
Introduction
1.3.1
Preview Activity
1.3.2
Truth Tables
1.3.3
Logical Equivalence
1.3.4
Deductions
1.3
Reading Questions
1.3
Practice Problems
1.3
Additional Exercises
1.4
Proofs
chevron_left
1.4.1
Introduction
1.4.2
Direct Proof
1.4.3
Proof by Contrapositive
1.4.4
Proof by Contradiction
1.4.5
Summary of Proof Styles
1.4
Reading Questions
1.4
Practice Problems
1.4
Additional Exercises
1.5
Proofs about Discrete Structures
chevron_left
1.5.1
Introduction
1.5.2
Proofs about sets
1.5.3
Proofs about functions
1.5.4
Proofs about relations
1.5.5
Proofs about graphs
1.6
Chapter Summary
chevron_left
1.6
Chapter Review
2
Graph Theory
chevron_left
2.1
Definitions
chevron_left
2.1
Reading Questions
2.1
Practice Problems
2.1
Exercises
2.2
Trees
chevron_left
2.2.1
Properties of Trees
2.2.2
Rooted Trees
2.2.3
Spanning Trees
2.2
Reading Questions
2.2
Practice Problems
2.2
Additional Exercises
2.3
Planar Graphs
chevron_left
2.3.1
Non-planar Graphs
2.3.2
Polyhedra
2.3
Reading Questions
2.3
Practice Problems
2.3
Additional Exercises
2.4
Euler Trails and Circuits
chevron_left
2.4.1
Hamilton Paths
2.4
Reading Questions
2.4
Practice Problems
2.4
Additional Exercises
2.5
Coloring
chevron_left
2.5.1
Coloring in General
2.5.2
Coloring Edges
2.5
Reading Questions
2.5
Practice Problems
2.5
Additional Exercises
2.6
Relations and Graphs
chevron_left
2.6.1
Relations Generally
2.6.2
Properties of Relations
2.6.3
Equivalence Relations
2.6.4
Equivalence Classes and Partitions
2.6
Reading Questions
2.6
Practice Problems
2.6
Additional Exercises
2.7
Matching in Bipartite Graphs
chevron_left
2.7
Exercises
2.8
Chapter Summary
chevron_left
2.8
Chapter Review
3
Counting
chevron_left
3.1
Pascal’s Arithmetical Triangle
chevron_left
3.1.1
Lattice Paths
3.1.2
Bit Strings
3.1.3
Subsets and Pizzas
3.1.4
Algebra?
3.1
Reading Questions
3.1
Practice Problems
3.1
Additional Exercises
3.2
Combining Outcomes
chevron_left
3.2.1
What are we combining?
3.2.2
The Sum and Product Principles
3.2.3
Combining principles
3.2
Reading Questions
3.2
Practice Problems
3.2
Additional Exercises
3.3
Non-Disjoint Outcomes
chevron_left
3.3.1
Counting with Venn Diagrams
3.3.2
The Principle of Inclusion/Exclusion
3.3.3
Overlaps and the Product Principle
3.3
Reading Questions
3.3
Practice Problems
3.3
Additional Exercises
3.4
Combinations and Permutations
chevron_left
3.4
Reading Questions
3.4
Practice Problems
3.4
Additional Exercises
3.5
Counting Multisets
chevron_left
3.5
Reading Questions
3.5
Practice Problems
3.5
Additional Exercises
3.6
Combinatorial Proofs
chevron_left
3.6.1
Patterns in Pascal’s Triangle
3.6.2
More Proofs
3.6
Reading Questions
3.6
Exercises
3.6
Activity: Combinatorial Proofs
3.7
Applications to Probability
chevron_left
3.7.1
Computing Probabilities
3.7.2
Probability Rules
3.7.3
Conditional Probability
3.7
Reading Questions
3.7
Practice Problems
3.7
Additional Exercises
3.8
Advanced Counting Using PIE
chevron_left
3.8.1
Counting Derangements
3.8.2
Counting Functions
3.8
Exercises
3.9
Chapter Summary
chevron_left
3.9
Chapter Review
4
Sequences
chevron_left
4.1
Describing Sequences
chevron_left
4.1
Reading Questions
4.1
Practice Problems
4.1
Additional Exercises
4.2
Rate of Growth
chevron_left
4.2.1
Arithmetic and Geometric Sequences
4.2.2
Arithmetic and Geometric Rates of Change
Summing Arithmetic Sequences: Reverse and Add
Summing Geometric Sequences: Multiply, Shift and Subtract
4.2
Reading Questions
4.2
Practice Problems
4.2
Additional Exercises
4.3
Polynomial Sequences
chevron_left
4.3
Reading Questions
4.3
Exercises
4.3
Additional Exercises
4.4
Solving Recurrence Relations
chevron_left
4.4.1
The Characteristic Root Technique
4.4
Reading Questions
4.4
Practice Problems
4.4
Additional Exercises
4.5
Proof by Induction
chevron_left
4.5.1
Preview
4.5.2
Recursive Reasoning
4.5.3
Formalizing Proofs
4.5.4
Examples
4.5
Reading Questions
4.5
Practice Problems
4.5
Additional Exercises
4.6
Strong Induction
chevron_left
4.6.1
Going farther back
4.6
Reading Questions
4.6
Practice Problems
4.6
Additional Exercises
4.7
Chapter Summary
chevron_left
4.7
Chapter Review
5
Discrete Structures Revisited
chevron_left
5.1
Sets
chevron_left
5.1.1
Notation
5.1.2
Relationships Between Sets
5.1.3
Operations On Sets
5.1.4
Venn Diagrams
5.1
Exercises
5.2
Functions
chevron_left
5.2.1
Describing Functions
5.2.2
Surjections, Injections, and Bijections
5.2.3
Image and Inverse Image
5.2.3
Reading Questions
5.2
Exercises
6
Additional Topics
chevron_left
6.1
Generating Functions
chevron_left
6.1.1
Building Generating Functions
6.1.2
Differencing
6.1.3
Multiplication and Partial Sums
6.1.4
Solving Recurrence Relations with Generating Functions
6.1
Exercises
6.2
Introduction to Number Theory
chevron_left
6.2.1
Divisibility
6.2.2
Remainder Classes
6.2.3
Properties of Congruence
6.2.4
Solving Congruences
6.2.5
Solving Linear Diophantine Equations
6.2
Exercises
Backmatter
chevron_left
A
Peer Instruction Questions
chevron_left
A.1
Introduction and Preliminaries
A.1.1
What is Discrete Mathematics
A.1.2
Discrete Structures
A.1.3
Sets
A.1.4
Functions
A.2
Symbolic Logic and Proofs
A.2.1
Mathematical Statements
A.2.2
Propositional Logic
A.2.3
Proofs
A.3
Graph Theory
A.4
Counting
A.5
Sequences
A.6
Additional Topics
B
Selected Hints
C
Selected Solutions
D
List of Symbols
Index
Colophon
🔗
Colophon
Colophon
🔗
This book was authored in PreTeXt.
