Skip to main content
Discrete Mathematics:
An Open Introduction, 4th edition
Oscar Levin
Contents
Index
Search Book
close
Search Results:
No results.
Prev
Up
Next
\(\usepackage{cancel} \def\d{\displaystyle} \def\N{\mathbb N} \def\B{\mathbf B} \def\Z{\mathbb Z} \def\Q{\mathbb Q} \def\R{\mathbb R} \def\C{\mathbb C} \def\U{\mathcal U} \def\x{\mathbf{x}} \def\y{\mathbf{y}} \def\X{\mathcal{X}} \def\Y{\mathcal{Y}} \def\pow{\mathcal P} \def\inv{^{-1}} \def\st{:} \def\iff{\leftrightarrow} \def\Iff{\Leftrightarrow} \def\imp{\rightarrow} \def\Imp{\Rightarrow} \def\isom{\cong} \def\bar{\overline} \def\card#1{\left| #1 \right|} \def\twoline#1#2{\begin{pmatrix}#1 \\ #2 \end{pmatrix}} \def\mchoose#1#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{\circ} \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
Reading Questions
1
Logic and Proofs
1.1
Mathematical Statements
Section Preview
Preview Activity
Atomic and Molecular Statements
Quantifiers and Predicates
Reading Questions
Practice Problems
Additional Exercises
1.2
Implications
Section Preview
Preview Activity
Understanding the Truth Table
Related Statements
Reading Questions
Practice Problems
Additional Exercises
1.3
Rules of Logic
Section Preview
Preview Activity
Truth Tables
Logical Equivalence
Equivalence for Quantified Statements
Deductions
Reading Questions
Practice Problems
Additional Exercises
1.4
Proofs
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
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
1.6
Chapter Review
2
Graph Theory
2.1
Problems and Definitions
Section Preview
Preview Activity
What is a Graph?
Reading Questions
Practice Problems
Additional Exercises
2.2
Trees
Section Preview
Preview Activity
Properties of Trees
Spanning Trees
Rooted Trees
Reading Questions
Practice Problems
Additional Exercises
2.3
Planar Graphs
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
Section Preview
Preview Activity
Conditions for Euler Trials
Hamilton Paths
Reading Questions
Practice Problems
Additional Exercises
2.5
Coloring
Section Preview
Preview Activity
Coloring Vertices
Coloring Edges
Reading Questions
Practice Problems
Additional Exercises
2.6
Relations and Graphs
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
2.7
Exercises
2.8
Chapter Summary
2.8
Chapter Review
3
Counting
3.1
Pascal’s Arithmetical Triangle
Section Preview
Preview Activity
Lattice Paths
Bit Strings
Subsets and Pizzas
Algebra?
Reading Questions
Practice Problems
Additional Exercises
3.2
Combining Outcomes
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
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
Section Preview
Preview Activity
Counting Sequences
Counting Sets
The Quotient Principle
Reading Questions
Practice Problems
Additional Exercises
3.5
Counting Multisets
Section Preview
Preview Activity
Have some cookies
Representing multisets with bit strings
Reading Questions
Practice Problems
Additional Exercises
3.6
Combinatorial Proofs
Section Preview
Preview Activity
Patterns in Pascal’s Triangle
More Proofs
Reading Questions
Practice Problems
Additional Exercises
3.7
Applications to Probability
Section Preview
Preview Activity
Computing Probabilities
Probability Rules
Conditional Probability
Reading Questions
Practice Problems
Additional Exercises
3.8
Advanced Counting Using PIE
Section Preview
Preview Activity
PIE for multisets
Counting Derangements
Counting Functions
Practice Problems
Additional Exercises
3.9
Chapter Summary
3.9
Chapter Review
4
Sequences
4.1
Describing Sequences
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
Section Preview
Preview Activity
Arithmetic Sequences
Geometric Sequences
Beyond Arithmetic and Geometric Sequences
Reading Questions
Practice Problems
Additional Exercises
4.3
Polynomial Sequences
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
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
Section Preview
Preview Activity
Recursive Reasoning
Formalizing Proofs
Examples
Reading Questions
Practice Problems
Additional Exercises
4.6
Strong Induction
Section Preview
Preview Activity
Divide and conquer
Reading Questions
Practice Problems
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
Exercises
5.2
Functions
Describing Functions
Surjections, Injections, and Bijections
Image and Inverse Image
Reading Questions
Exercises
6
Additional Topics
6.1
Generating Functions
Building Generating Functions
Differencing
Multiplication and Partial Sums
Solving Recurrence Relations with Generating Functions
Exercises
6.2
Introduction to Number Theory
Divisibility
Remainder Classes
Properties of Congruence
Solving Congruences
Solving Linear Diophantine Equations
Exercises
Backmatter
A
Selected Hints
B
Selected Solutions
C
List of Symbols
Index
Colophon
Colophon
Colophon
This book was authored in PreTeXt.