**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