You are here

Discrete Mathematics with Ducks

sarah-marie belcastro
Publisher: 
Chapman & Hall/CRC
Publication Date: 
2012
Number of Pages: 
538
Format: 
Hardcover
Price: 
59.95
ISBN: 
9781466504998
Category: 
Textbook
[Reviewed by
Charles Ashbacher
, on
08/22/2012
]

There are many textbooks that can be used in discrete mathematics classes; this one has some unique features, of which one is the many references to ducks. As I looked through the book and approached new topics, my mind drifted to wondering whether the author would use another play on words involved web-footed fowl. For example, when the topic of induction began, my mind wandered to the word “inducktion”, wondering if it would be used. Images of ducks with pencils on their shoulders are used throughout to label positions where there are exercises to work through.

Some of the worked examples and exercises contain a reference to ducks, for example, “How many ways can you select 2 ducks from a flock of 9?” Through the references to ducks, serious and effective mathematical instruction is achieved. The coverage is pretty standard for discrete mathematics courses; the only unusual addition was the section on transfinite numbers. It was presented as a play featuring a set of duck droppings and a modified Hilbert Hotel, which is quite a combination.

There are three sections, each labeled with a theme. They are:

  • The basics
  • Combinatorics
  • Graph theory
  • Other material: probability and cardinality.

Graph theory is strongly emphasized; it is the primary topic of 5 of the fifteen chapters. The sections on the basics of set theory and logic are brief, a total of 30 pages. It includes the amusing and quite “natural” use of ducks that only tell the truth and others that only lie. There are some proofs, but probably not enough to satisfy the instructor that wants to emphasize the mathematics.

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 splits his time between consulting with industry in projects involving math and computers, teaching college classes and co-editing The Journal of Recreational Mathematics. In his spare time, he reads about these things and helps his daughter in her lawn care business.

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