Skip to main content
Discrete Mathematics:
An Open Introduction, 4th Edition
Oscar Levin
Contents
Index
Search Book
close
Search Results:
No results.
dark_mode
Dark Mode
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
\usepackage
\usepackage
c
a
n
c
e
l
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
Introduction
Sets
Functions
Sequences
Relations
Graphs
Even More Structures
Reading Questions
1
Logic and Proofs
chevron_left
1.1
Mathematical Statements
chevron_left
Section Preview
Preview Activity
Atomic and Molecular Statements
Quantifiers and Predicates
Reading Questions
Practice Problems
Additional Exercises
1.2
Implications
chevron_left
Section Preview
Preview Activity
Understanding the Truth Table
Related Statements
Reading Questions
Practice Problems
Additional Exercises
1.3
Rules of Logic
chevron_left
Section Preview
Preview Activity
Truth Tables
Logical Equivalence
Equivalence for Quantified Statements
Deductions
Reading Questions
Practice Problems
Additional Exercises
1.4
Proofs
chevron_left
Section Preview
Preview Activity
Direct Proof
Proof by Contrapositive
Proof by Contradiction
Summary of Proof Styles
Reading Questions
Practice Problems
Additional Exercises
1.5
Proofs about Discrete Structures
chevron_left
Section Preview
Preview Activity
Proofs about Sets
Proofs about Functions
Proofs about Relations
Proofs about Graphs
Reading Questions
Practice Problems
Additional Exercises
1.6
Chapter Summary
chevron_left
1.6
Chapter Review
2
Graph Theory
chevron_left
2.1
Problems and Definitions
chevron_left
Section Preview
Preview Activity
What is a Graph?
Reading Questions
Practice Problems
Additional Exercises
2.2
Trees
chevron_left
Section Preview
Preview Activity
Properties of Trees
Spanning Trees
Rooted Trees
Reading Questions
Practice Problems
Additional Exercises
2.3
Planar Graphs
chevron_left
Section Preview
Preview Activity
Euler’s Formula for Planar Graphs
Non-planar Graphs
Polyhedra
Reading Questions
Practice Problems
Additional Exercises
2.4
Euler Trails and Circuits
chevron_left
Section Preview
Preview Activity
Conditions for Euler Trails
Hamilton Paths
Reading Questions
Practice Problems
Additional Exercises
2.5
Coloring
chevron_left
Section Preview
Preview Activity
Coloring Vertices
Coloring Edges
Reading Questions
Practice Problems
Additional Exercises
2.6
Relations and Graphs
chevron_left
Section Preview
Preview Activity
Relations Generally
Properties of Relations
Equivalence Relations
Equivalence Classes and Partitions
Reading Questions
Practice Problems
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
Section Preview
Preview Activity
Lattice Paths
Bit Strings
Subsets and Pizzas
Algebra?
Reading Questions
Practice Problems
Additional Exercises
3.2
Combining Outcomes
chevron_left
Section Preview
Preview Activity
What are
Outcomes
?
The Sum and Product Principles
Combining Principles
Reading Questions
Practice Problems
Additional Exercises
3.3
Non-Disjoint Outcomes
chevron_left
Section Preview
Preview Activity
Counting with Venn Diagrams
The Principle of Inclusion/Exclusion
Overlaps and the Product Principle
Reading Questions
Practice Problems
Additional Exercises
3.4
Combinations and Permutations
chevron_left
Section Preview
Preview Activity
Counting Sequences
Counting Sets
The Quotient Principle
Reading Questions
Practice Problems
Additional Exercises
3.5
Counting Multisets
chevron_left
Section Preview
Preview Activity
Have Some Cookies
Representing Multisets with Bit Strings
Reading Questions
Practice Problems
Additional Exercises
3.6
Combinatorial Proofs
chevron_left
Section Preview
Preview Activity
Patterns in Pascal’s Triangle
More Proofs
Reading Questions
Practice Problems
Additional Exercises
3.7
Applications to Probability
chevron_left
Section Preview
Preview Activity
Computing Probabilities
Probability Rules
Conditional Probability
Reading Questions
Practice Problems
Additional Exercises
3.8
Advanced Counting Using PIE
chevron_left
Section Preview
Preview Activity
PIE for Multisets
Counting Derangements
Counting Functions
Practice Problems
Additional Exercises
3.9
Chapter Summary
chevron_left
3.9
Chapter Review
4
Sequences
chevron_left
4.1
Describing Sequences
chevron_left
Section Preview
Preview Activity
Sequences and Formulas
Partial Sums and Differences
Sequences in python
Reading Questions
Practice Problems
Additional Exercises
4.2
Rate of Growth
chevron_left
Section Preview
Preview Activity
Arithmetic Sequences
Geometric Sequences
Beyond Arithmetic and Geometric Sequences
Reading Questions
Practice Problems
Additional Exercises
4.3
Polynomial Sequences
chevron_left
Section Preview
Preview Activity
Summing Arithmetic Sequences: Reverse and Add
Higher Degree Polynomials
Solving Systems of Equations with Technology
Reading Questions
Practice Problems
Additional Exercises
4.4
Exponential Sequences
chevron_left
Section Preview
Preview Activity
Summing Geometric Sequences: Multiply, Shift, and Subtract
The Characteristic Root Technique
Reading Questions
Practice Problems
Additional Exercises
4.5
Proof by Induction
chevron_left
Section Preview
Preview Activity
Recursive Reasoning
Formalizing Proofs
Examples
Reading Questions
Practice Problems
Additional Exercises
4.6
Strong Induction
chevron_left
Section Preview
Preview Activity
Divide and Conquer
Reading Questions
Practice Problems
Additional Exercises
4.7
Chapter Summary
chevron_left
4.7
Chapter Review
5
Discrete Structures Revisited
chevron_left
5.1
Sets
chevron_left
Notation
Relationships between Sets
Operations on Sets
Venn Diagrams
Exercises
5.2
Functions
chevron_left
Describing Functions
Surjections, Injections, and Bijections
Image and Inverse Image
Reading Questions
Exercises
6
Additional Topics
chevron_left
6.1
Generating Functions
chevron_left
Building Generating Functions
Differencing
Multiplication and Partial Sums
Solving Recurrence Relations with Generating Functions
Exercises
6.2
Introduction to Number Theory
chevron_left
Divisibility
Remainder Classes
Properties of Congruence
Solving Congruences
Solving Linear Diophantine Equations
Exercises
Backmatter
chevron_left
A
Selected Hints
B
Selected Solutions
C
List of Symbols
Index
Colophon
Discrete Mathematics:
An Open Introduction, 4th Edition
Oscar Levin
Mathematical Sciences
University of Northern Colorado
Fall 2024
Colophon
Dedication
Acknowledgements
Preface
How to Use This Book
🔗
