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
Scratch ActiveCode
Profile
Course Home
Assignments
Practice
Peer Instruction (Instructor)
Peer Instruction (Student)
Change Course
Instructor's Page
Progress Page
Edit Profile
Change Password
Log Out
\(\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
Introduction
Sets
Functions
Sequences
Relations
Graphs
Even More Structures
0.2
Reading Questions
1
Symbolic Logic and Proofs
1.1
Mathematical Statements
Introduction
Preview Activity
Atomic and Molecular Statements
Implications
1.1
Reading Questions
1.1
Practice Problems
1.1
Additional Exercises
1.2
Propositional Logic
Introduction
Preview Activity
Truth Tables
Logical Equivalence
Deductions
1.2
Reading Questions
1.2
Practice Problems
1.2
Additional Exercises
1.3
Quantifiers and Predicate Logic
Beyond Propositions
Preview Activity
Statements with variables
1.3
Reading Questions
1.3
Practice Problems
1.3
Additional Exercises
1.4
Proofs
Introduction
Direct Proof
Proof by Contrapositive
Proof by Contradiction
Proof by (counter) Example
Proof by Cases
1.4
Reading Questions
1.4
Practice Problems
1.4
Additional Exercises
1.5
Proofs about Discrete Structures
Introduction
Proofs about sets
Proofs about functions
Proofs about relations
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
Properties of Trees
Rooted Trees
Spanning Trees
2.2
Reading Questions
2.2
Practice Problems
2.2
Additional Exercises
2.3
Planar Graphs
Non-planar Graphs
Polyhedra
2.3
Reading Questions
2.3
Practice Problems
2.3
Additional Exercises
2.4
Euler Trails and Circuits
Hamilton Paths
2.4
Reading Questions
2.4
Practice Problems
2.4
Additional Exercises
2.5
Coloring
Coloring in General
Coloring Edges
2.5
Reading Questions
2.5
Practice Problems
2.5
Additional Exercises
2.6
Relations and Graphs
Relations Generally
Properties of Relations
Equivalence Relations
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
Additive and Multiplicative Principles
Counting With Sets
Principle of Inclusion/Exclusion
3.1
Reading Questions
3.1
Practice Problems
3.1
Additional Exercises
3.2
Binomial Coefficients
Subsets
Bit Strings
Lattice Paths
Binomial Coefficients
Pascal’s Triangle
3.2
Reading Questions
3.2
Practice Problems
3.3
Combinations and Permutations
3.3
Reading Questions
3.3
Practice Problems
3.3
Additional Exercises
3.4
Counting Multisets
3.4
Reading Questions
3.4
Practice Problems
3.4
Additional Exercises
3.5
Combinatorial Proofs
Patterns in Pascal’s Triangle
More Proofs
3.5
Reading Questions
3.5
Exercises
3.5
Activity: Combinatorial Proofs
3.6
Advanced Counting Using PIE
Counting Derangements
Counting Functions
3.6
Exercises
3.7
Chapter Summary
3.7
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
Arithmetic and Geometric Sequences
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
The Characteristic Root Technique
4.4
Reading Questions
4.4
Practice Problems
4.4
Additional Exercises
4.5
Induction
Stamps
Formalizing Proofs
Examples
Strong Induction
4.5
Reading Questions
4.5
Practice Problems
4.5
Additional Exercises
4.6
Chapter Summary
4.6
Chapter Review
5
Discrete Structures Revisited
5.1
Sets
Notation
Relationships Between Sets
Operations On Sets
Venn Diagrams
5.1
Exercises
5.2
Functions
Describing Functions
Surjections, Injections, and Bijections
Image and Inverse Image
Reading Questions
5.2
Exercises
6
Additional Topics
6.1
Generating Functions
Building Generating Functions
Differencing
Multiplication and Partial Sums
Solving Recurrence Relations with Generating Functions
6.1
Exercises
6.2
Introduction to Number Theory
Divisibility
Remainder Classes
Properties of Congruence
Solving Congruences
Solving Linear Diophantine Equations
6.2
Exercises
Backmatter
A
Peer Instruction Questions
A.1
Introduction and Preliminaries
What is Discrete Mathematics
Discrete Structures
Sets
Functions
A.2
Symbolic Logic and Proofs
Mathematical Statements
Propositional Logic
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.