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.
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
Ask a Question About this Product More... |