Table of Contents

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.

Reviews

This book can certainly be used to teach the standard course in discrete mathematics designed for computer science majors. The lighter touch of duck references does amuse you and does not ever overshadow or disguise the mathematical concepts.
—Charles Ashbacher, MAA Reviews, August 2012 When I used Discrete Mathematics with Ducks in class, I assigned readings, and my students came to class full of questions and ideas. Every day we had a good time in one way or another; these classes were a highlight of my teaching career. I give a lot of credit to this book, thanks to the author's skill at blending rigor, great examples, casual humor, and precise writing.
—David Perkins, author of Calculus and Its Origins I had a lot of fun teaching from Discrete Mathematics with Ducks! ... I think the discovery/exploratory/problem solving approach is ABSOLUTELY the way this course should be taught, and of all the discrete books I have looked at, this text does the best job of supporting that kind of approach to the subject while still giving enough of the material in writing to fill in the gaps. ... I found that the material provided and the instructor notes cut down on my prep time, and I definitely referred to them. Having the in-class activities included is a huge benefit to this book.
—Dana Rowland, Associate Professor of Mathematics, Merrimack College ... an incredible book ... readable by students, useful for instructors, and constructed with style and flair. This book will make it much easier to teach an exciting, student-centered discrete mathematics course that will also serve as an excellent introduction to advanced critical thinking, problem solving, and proofs. And there are ducks!
—Douglas Shaw, Professor of Mathematics, University of Northern Iowa