Skip to main content
Discrete Mathematics:
An Open Introduction, 3rd edition
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{\vtx}[2]{node[fill,circle,inner sep=0pt, minimum size=4pt,label=#1:#2]{}} \newcommand{\va}[1]{\vtx{above}{#1}} \newcommand{\vb}[1]{\vtx{below}{#1}} \newcommand{\vr}[1]{\vtx{right}{#1}} \newcommand{\vl}[1]{\vtx{left}{#1}} \renewcommand{\v}{\vtx{above}{}} \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.2
Mathematical Statements
Atomic and Molecular Statements
Implications
Predicates and Quantifiers
0.2
Exercises
0.3
Sets
Notation
Relationships Between Sets
Operations On Sets
Venn Diagrams
0.3
Exercises
0.4
Functions
Describing Functions
Surjections, Injections, and Bijections
Image and Inverse Image
0.4
Exercises
1
Counting
1.1
Additive and Multiplicative Principles
Counting With Sets
Principle of Inclusion/Exclusion
1.1
Exercises
1.2
Binomial Coefficients
Subsets
Bit Strings
Lattice Paths
Binomial Coefficients
Pascal’s Triangle
1.2
Exercises
1.3
Combinations and Permutations
1.3
Exercises
1.4
Combinatorial Proofs
Patterns in Pascal’s Triangle
More Proofs
1.4
Exercises
1.5
Stars and Bars
1.5
Exercises
1.6
Advanced Counting Using PIE
Counting Derangements
Counting Functions
1.6
Exercises
1.7
Chapter Summary
1.7
Chapter Review
2
Sequences
2.1
Describing Sequences
2.1
Exercises
2.2
Arithmetic and Geometric Sequences
Sums of Arithmetic and Geometric Sequences
Summing Arithmetic Sequences: Reverse and Add
Summing Geometric Sequences: Multiply, Shift and Subtract
2.2
Exercises
2.3
Polynomial Fitting
2.3
Exercises
2.4
Solving Recurrence Relations
The Characteristic Root Technique
2.4
Exercises
2.5
Induction
Stamps
Formalizing Proofs
Examples
Strong Induction
2.5
Exercises
2.6
Chapter Summary
2.6
Chapter Review
3
Symbolic Logic and Proofs
3.1
Propositional Logic
Truth Tables
Logical Equivalence
Deductions
Beyond Propositions
3.1
Exercises
3.2
Proofs
Direct Proof
Proof by Contrapositive
Proof by Contradiction
Proof by (counter) Example
Proof by Cases
3.2
Exercises
3.3
Chapter Summary
3.3
Chapter Review
4
Graph Theory
4.1
Definitions
4.1
Exercises
4.2
Trees
Properties of Trees
Rooted Trees
Spanning Trees
4.2
Exercises
4.3
Planar Graphs
Non-planar Graphs
Polyhedra
4.3
Exercises
4.4
Coloring
Coloring in General
Coloring Edges
4.4
Exercises
4.5
Euler Paths and Circuits
Hamilton Paths
4.5
Exercises
4.6
Matching in Bipartite Graphs
4.6
Exercises
4.7
Chapter Summary
4.7
Chapter Review
5
Additional Topics
5.1
Generating Functions
Building Generating Functions
Differencing
Multiplication and Partial Sums
Solving Recurrence Relations with Generating Functions
5.1
Exercises
5.2
Introduction to Number Theory
Divisibility
Remainder Classes
Properties of Congruence
Solving Congruences
Solving Linear Diophantine Equations
5.2
Exercises
Backmatter
A
Selected Hints
B
Selected Solutions
C
List of Symbols
Index
Colophon
Colophon
Colophon
This book was authored in PreTeXt.
