- Balances mathematics and computer science
- Follows basic curriculum outlined by SIGCSE guidelines
- Includes classroom activities and notes for instructors

*Solutions manual is available upon qualifying course adoption.*

Containing exercises and materials that engage students at all levels,** Discrete Mathematics with Ducks** presents a gentle introduction for students who find the proofs and abstractions of mathematics challenging. This classroom-tested text uses discrete mathematics as the context for introducing proofwriting.

Facilitating effective and active learning, each chapter contains a mixture of discovery activities, expository text, in-class exercises, and homework problems.

- Elementary exercises at the end of each expository section prompt students to review the material
*Try This!*sections encourage students to construct fundamental components of the concepts, theorems, and proofs discussed.- Sets of discovery problems and illustrative examples reinforce learning.
- Bonus sections can be used for take-home exams, projects, or further study
- Instructor Notes sections offer suggestions on how to use the material in each chapter

**Discrete Mathematics with Ducks** offers students a diverse introduction to the field and a solid foundation for further study in discrete mathematics and complies with SIGCSE guidelines. The book shows how combinatorics and graph theory are used in both computer science and mathematics.

**THE BASICS**Counting and Proofs

Introduction and Summary

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

**COMBINATORICSBinomial Coefficients and Pascal’s Triangle**

Introduction and Summary

You Have a Choice

Pascal’s Triangle

Overcounting Carefully and Reordering at Will

Try This! Play with Powers and Permutations

Binomial Basics

Combinatorial Proof

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

Yam, Spaghetti and Pizza Numbers

Where to Go from Here

Bonus: Geometric Gems

**GRAPH THEORYTrees**

Introduction and Summary

Basic Facts about Trees

Spanning Tree Algorithms

Binary Trees

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 MATERIALProbability and Expectation**

Introduction and Summary

What

High Expectations

You are Probably Expected to

Conditional Probability and Independence

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

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