Discrete Mathematics with Ducks

THE BASICS
Counting and Proofs
Introduction and Summary
Try This! Let’s Count
The Sum and Product Principles
Preliminaries on Proofs and Disproofs
Pigeons and Correspondences
Where to Go from Here





Sets and Logic
Introduction and Summary
Sets
Logic
Try This! Problems on Sets and Logic
Proof Techniques: Not!
Try This! A Tricky Conundrum
Where to Go from Here
Bonus: Truth Tellers





Graphs and Functions
Introduction and Summary
Function Introduction
Try This! Play with Functions and Graphs
Functions and Counting
Graphs: Definitions and Examples
Isomorphisms
Graphs: Operations and Uses
Try This! More Graph Problems
Ramseyness
Where to Go from Here
Bonus: Party Tricks
Bonus 2: Counting with the Characteristic Function





Induction
Introduction and Summary
Induction
Try This! Induction
More Examples
The Best Inducktion Proof Ever
Try This! More Problems about Induction
Are They or Aren’t They? Resolving Grey Ducks
Where to Go from Here
Bonus: Small Crooks
Bonus 2: An Induction Song





Algorithms with Ciphers
Introduction and Summary
Algorithms
Modular Arithmetic (and Equivalence Relations)
Cryptography: Some Ciphers
Try This! Encryptoequivalent Modulagorithmic Problems
Where to Go from Here
Bonus: Algorithms for Searching Graphs
Bonus 2: Pigeons and Divisibility





COMBINATORICS
Binomial Coefficients and Pascal’s Triangle
Introduction and Summary
You Have a Choice
Try This! Investigate a Triangle
Pascal’s Triangle
Overcounting Carefully and Reordering at Will
Try This! Play with Powers and Permutations
Binomial Basics
Combinatorial Proof
Try This! Pancakes and Proofs
Where to Go from Here
Bonus: Sorting Bubbles in Order of Size
Bonus 2: Mastermind





Balls and Boxes and PIE—Counting Techniques
Introduction and Summary
Combinatorial Problem Types
Try This! Let’s Have Some PIE
Combinatorial Problem Solutions and Strategies
Let’s Explain Our PIE!
Try This! What Are the Balls and What Are the Boxes? And Do You Want Some PIE?
Where to Go from Here
Bonus: Linear and Integer Programming





Recurrences
Introduction and Summary
Fibonacci Numbers and Identities
Recurrences and Integer Sequences and Induction
Try This! Sequences and Fibonacci Identities
Naive Techniques for Finding Closed Forms and Recurrences
Arithmetic Sequences and Finite Differences
Try This! Recurrence Exercises
Geometric Sequences and the Characteristic Equation
Try This! Find Closed Forms for These Recurrence Relations!
Where to Go from Here
Bonus: Recurring Stories





Cutting up Food (Counting and Geometry)
Introduction and Summary
Try This! Slice Pizza (and a Yam)
Pizza Numbers
Try This! Spaghetti, Yams, and More
Yam, Spaghetti and Pizza Numbers
Where to Go from Here
Bonus: Geometric Gems





GRAPH THEORY
Trees
Introduction and Summary
Basic Facts about Trees
Try This! Spanning Trees
Spanning Tree Algorithms
Binary Trees
Try This! Binary Trees and Matchings
Matchings
Backtracking
Where to Go from Here
Bonus: The Branch-and-Bound Technique in Integer Programming





Euler’s Formula and Applications
Introduction and Summary
Try This! Planarity Explorations
Planarity
A Lovely Story
Or, Are Emus Full?: A Theorem and a Proof
Applications of Euler’s Formula
Try This! Applications of Euler’s Formula
Where to Go from Here
Bonus: Topological Graph Theory





Graph Traversals
Introduction and Summary
Try This! Euler Traversals
Euler Paths and Circuits
Hamilton Circuits, the Traveling Salesperson Problem, and Dijkstra’s Algorithm
Try This!—Do This!—Try This!
Where to Go from Here
Bonus: Digraphs, Euler Traversals, and RNA Chains
Bonus 2: Network Flows
Bonus 3: Two Hamiltonian Theorems





Graph Coloring
Introduction and Summary
Try This! Coloring Vertices and Edges
Introduction to Coloring
Try This! Let’s Think about Coloring
Coloring and Things (Graphs and Concepts) That Have Come Before
Where to Go from Here
Bonus: The Four-Color Theorem





OTHER MATERIAL
Probability and Expectation
Introduction and Summary
What Is Probability, Exactly?
High Expectations
You are Probably Expected to Try This!
Conditional Probability and Independence
Try This! . . . Probably, Under Certain Conditions
Higher Expectations
Where to Go from Here
Bonus: Ramsey Numbers and the Probabilistic Method





Fun with Cardinality
Introduction and Summary
Read This! Parasitology, The Play
How Big Is Infinite?
Try This! Investigating the Play
How High Can We Count?
Where to Go from Here
Bonus: The Schröder–Bernstein Theorem





Additional Problems


Solutions to Check Yourself Problems


The Greek Alphabet and Some Uses for Some Letters


List of Symbols


Glossary


Bibliography





Problems and Instructor Notes appear at the end of each chapter.