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
\(\renewcommand{\d}{\displaystyle} \newcommand{\N}{\mathbb N} \newcommand{\B}{\mathbf B} \newcommand{\Z}{\mathbb Z} \newcommand{\Q}{\mathbb Q} \newcommand{\R}{\mathbb R} \newcommand{\C}{\mathbb C} \newcommand{\U}{\mathcal U} \newcommand{\pow}{\mathcal P} \newcommand{\inv}{^{-1}} \newcommand{\st}{:} \renewcommand{\iff}{\leftrightarrow} \newcommand{\Iff}{\Leftrightarrow} \newcommand{\imp}{\rightarrow} \newcommand{\Imp}{\Rightarrow} \newcommand{\isom}{\cong} \renewcommand{\bar}{\overline} \newcommand{\card}[1]{\left| #1 \right|} \newcommand{\twoline}[2]{\begin{pmatrix}#1 \\ #2 \end{pmatrix}} \newcommand{\mchoose}[2]{ \left.\mathchoice {\left(\kern-0.48em\binom{#1}{#2}\kern-0.48em\right)} {\big(\kern-0.30em\binom{\smash{#1}}{\smash{#2}}\kern-0.30em\big)} {\left(\kern-0.30em\binom{\smash{#1}}{\smash{#2}}\kern-0.30em\right)} {\left(\kern-0.30em\binom{\smash{#1}}{\smash{#2}}\kern-0.30em\right)} \right.} \def\o{\,o\,} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \definecolor{fillinmathshade}{gray}{0.9} \newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}} \)
Front Matter
Colophon
Dedication
Acknowledgements
Preface
How to use this book
0
Introduction and Preliminaries
0.1
What is Discrete Mathematics?
0.1
Reading Questions
0.2
Discrete Structures
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
1.1
Mathematical Statements
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
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
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
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
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
1.6
Chapter Review
2
Graph Theory
2.1
Definitions
2.1
Reading Questions
2.1
Practice Problems
2.1
Exercises
2.2
Trees
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
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
2.4.1
Hamilton Paths
2.4
Reading Questions
2.4
Practice Problems
2.4
Additional Exercises
2.5
Coloring
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
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
2.7
Exercises
2.8
Chapter Summary
2.8
Chapter Review
3
Counting
3.1
Pascal’s Arithmetical Triangle
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
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
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
3.4
Reading Questions
3.4
Practice Problems
3.4
Additional Exercises
3.5
Counting Multisets
3.5
Reading Questions
3.5
Practice Problems
3.5
Additional Exercises
3.6
Combinatorial Proofs
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
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
3.8.1
Counting Derangements
3.8.2
Counting Functions
3.8
Exercises
3.9
Chapter Summary
3.9
Chapter Review
4
Sequences
4.1
Describing Sequences
4.1
Reading Questions
4.1
Practice Problems
4.1
Additional Exercises
4.2
Rate of Growth
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
4.3
Reading Questions
4.3
Exercises
4.3
Additional Exercises
4.4
Solving Recurrence Relations
4.4.1
The Characteristic Root Technique
4.4
Reading Questions
4.4
Practice Problems
4.4
Additional Exercises
4.5
Proof by Induction
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
4.6.1
Going farther back
4.6
Reading Questions
4.6
Practice Problems
4.6
Additional Exercises
4.7
Chapter Summary
4.7
Chapter Review
5
Discrete Structures Revisited
5.1
Sets
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
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
6.1
Generating Functions
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
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
A
Peer Instruction Questions
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.
