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
Introduction
Sets
Functions
Sequences
Relations
Graphs
Even More Structures
1
Logic and Proofs
1.1
Mathematical Statements
Preview
Preview Activity
Atomic and Molecular Statements
Quantifiers and Predicates
1.1
Reading Questions
1.1
Practice Problems
1.1
Additional Exercises
1.2
Implications
Introduction
Understanding the Truth Table
Related Statements
1.2
Reading Questions
1.2
Practice Problems
1.2
Additional Exercises
1.3
Rules of Logic
Preview
Preview Activity
Truth Tables
Logical Equivalence
Deductions
1.3
Reading Questions
1.3
Practice Problems
1.3
Additional Exercises
1.4
Proofs
Introduction
Direct Proof
Proof by Contrapositive
Proof by Contradiction
Summary of Proof Styles
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
Problems and Definitions
Preview
2.1
Reading Questions
2.1
Practice Problems
2.1
Exercises
2.2
Trees
Properties of Trees
Spanning Trees
Rooted 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
Pascal’s Arithmetical Triangle
Lattice Paths
Bit Strings
Subsets and Pizzas
Algebra?
3.1
Reading Questions
3.1
Practice Problems
3.1
Additional Exercises
3.2
Combining Outcomes
What are we combining?
The Sum and Product Principles
Combining principles
3.2
Reading Questions
3.2
Practice Problems
3.2
Additional Exercises
3.3
Non-Disjoint Outcomes
Counting with Venn Diagrams
The Principle of Inclusion/Exclusion
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
Patterns in Pascal’s Triangle
More Proofs
3.6
Reading Questions
3.6
Exercises
3.6
Activity: Combinatorial Proofs
3.7
Applications to Probability
Computing Probabilities
Probability Rules
Conditional Probability
3.7
Reading Questions
3.7
Practice Problems
3.7
Additional Exercises
3.8
Advanced Counting Using PIE
Counting Derangements
Counting Functions
3.8
Exercises
3.9
Chapter Summary
3.9
Chapter Review
4
Sequences
4.1
Describing Sequences
Preview
Sequences and Formulas
Partial Sums and Differences
Sequences in python
4.1
Reading Questions
4.1
Practice Problems
4.1
Additional Exercises
4.2
Rate of Growth
Arithmetic and Geometric Sequences
4.2
Reading Questions
4.2
Practice Problems
4.2
Additional Exercises
4.3
Polynomial Sequences
Arithmetic and Geometric Rates of Change
Summing Arithmetic Sequences: Reverse and Add
Higher Degree Polynomials
Solving Systems of Equations with Technology
4.3
Reading Questions
4.3
Exercises
4.3
Additional Exercises
4.4
Exponential Sequences
Summing Geometric Sequences: Multiply, Shift and Subtract
The Characteristic Root Technique
4.4
Reading Questions
4.4
Practice Problems
4.4
Additional Exercises
4.5
Proof by Induction
Preview
Recursive Reasoning
Formalizing Proofs
Examples
4.5
Reading Questions
4.5
Practice Problems
4.5
Additional Exercises
4.6
Strong Induction
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
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
Selected Hints
B
Selected Solutions
C
List of Symbols
Index
Colophon
Colophon
Colophon
This book was authored in PreTeXt.