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
Introduction
Sets
Functions
Sequences
Relations
Graphs
Even More Structures
1
Logic and Proofs
chevron_left
1.1
Mathematical Statements
chevron_left
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
chevron_left
Introduction
Understanding the Truth Table
Related Statements
1.2
Reading Questions
1.2
Practice Problems
1.2
Additional Exercises
1.3
Rules of Logic
chevron_left
Preview
Preview Activity
Truth Tables
Logical Equivalence
Deductions
1.3
Reading Questions
1.3
Practice Problems
1.3
Additional Exercises
1.4
Proofs
chevron_left
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
chevron_left
Introduction
Proofs about sets
Proofs about functions
Proofs about relations
Proofs about graphs
1.6
Chapter Summary
chevron_left
1.6
Chapter Review
2
Graph Theory
chevron_left
2.1
Problems and Definitions
chevron_left
Preview
2.1
Reading Questions
2.1
Practice Problems
2.1
Exercises
2.2
Trees
chevron_left
Properties of Trees
Spanning Trees
Rooted Trees
2.2
Reading Questions
2.2
Practice Problems
2.2
Additional Exercises
2.3
Planar Graphs
chevron_left
Non-planar Graphs
Polyhedra
2.3
Reading Questions
2.3
Practice Problems
2.3
Additional Exercises
2.4
Euler Trails and Circuits
chevron_left
Hamilton Paths
2.4
Reading Questions
2.4
Practice Problems
2.4
Additional Exercises
2.5
Coloring
chevron_left
Coloring in General
Coloring Edges
2.5
Reading Questions
2.5
Practice Problems
2.5
Additional Exercises
2.6
Relations and Graphs
chevron_left
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
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
Lattice Paths
Bit Strings
Subsets and Pizzas
Algebra?
3.1
Reading Questions
3.1
Practice Problems
3.1
Additional Exercises
3.2
Combining Outcomes
chevron_left
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
chevron_left
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
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
Patterns in Pascal’s Triangle
More Proofs
3.6
Reading Questions
3.6
Exercises
3.6
Activity: Combinatorial Proofs
3.7
Applications to Probability
chevron_left
Computing Probabilities
Probability Rules
Conditional Probability
3.7
Reading Questions
3.7
Practice Problems
3.7
Additional Exercises
3.8
Advanced Counting Using PIE
chevron_left
Counting Derangements
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
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
chevron_left
Arithmetic and Geometric Sequences
4.2
Reading Questions
4.2
Practice Problems
4.2
Additional Exercises
4.3
Polynomial Sequences
chevron_left
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
chevron_left
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
chevron_left
Preview
Recursive Reasoning
Formalizing Proofs
Examples
4.5
Reading Questions
4.5
Practice Problems
4.5
Additional Exercises
4.6
Strong Induction
chevron_left
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
Notation
Relationships Between Sets
Operations On Sets
Venn Diagrams
5.1
Exercises
5.2
Functions
chevron_left
Describing Functions
Surjections, Injections, and Bijections
Image and Inverse Image
Reading Questions
5.2
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
6.1
Exercises
6.2
Introduction to Number Theory
chevron_left
Divisibility
Remainder Classes
Properties of Congruence
Solving Congruences
Solving Linear Diophantine Equations
6.2
Exercises
Backmatter
chevron_left
A
Selected Hints
B
Selected Solutions
C
List of Symbols
Index
Colophon
🔗
Front Matter
0
Introduction and Preliminaries
1
Logic and Proofs
2
Graph Theory
3
Counting
4
Sequences
5
Discrete Structures Revisited
6
Additional Topics
Backmatter
