How to Count : An Introduction to Combinatorics, Second Edition (Hardcover, 2 ed)

What’s It All About?
What Is Combinatorics?
Classic Problems
What You Need to Know
Are You Sitting Comfortably?

Permutations and Combinations
The Combinatorial Approach
Permutations
Combinations
Applications to Probability Problems
The Multinomial Theorem
Permutations and Cycles

Occupancy Problems
Counting the Solutions of Equations
New Problems from Old
A "Reduction" Theorem for the Stirling Numbers

The Inclusion-Exclusion Principle
Double Counting
Derangements
A Formula for the Stirling Numbers

Stirling and Catalan Numbers
Stirling Numbers
Permutations and Stirling Numbers
Catalan Numbers

Partitions and Dot Diagrams
Partitions
Dot Diagrams
A Bit of Speculation
More Proofs Using Dot Diagrams

Generating Functions and Recurrence Relations
Functions and Power Series
Generating Functions
What Is a Recurrence Relation?
Fibonacci Numbers
Solving Homogeneous Linear Recurrence Relations
Nonhomogeneous Linear Recurrence Relations
The Theory of Linear Recurrence Relations
Some Nonlinear Recurrence Relations

Partitions and Generating Functions
The Generating Function for the Partition Numbers
A Quick(ish) Way of Finding p(n)
An Upper Bound for the Partition Numbers
The Hardy?Ramanujan Formula
The Story of Hardy and Ramanujan

Introduction to Graphs
Graphs and Pictures
Graphs: A Picture-Free Definition
Isomorphism of Graphs
Paths and Connected Graphs
Planar Graphs
Eulerian Graphs
Hamiltonian Graphs
The Four-Color Theorem

Trees
What Is a Tree?
Labeled Trees
Spanning Trees and Minimal Connectors
The Shortest-Path Problem

Groups of Permutations
Permutations as Groups
Symmetry Groups
Subgroups and Lagrange’s Theorem
Orders of Group Elements
The Orders of Permutations

Group Actions
Colorings
The Axioms for Group Actions
Orbits
Stabilizers

Counting Patterns
Frobenius’s Counting Theorem
Applications of Frobenius’s Counting Theorem

Polya Counting
Colorings and Group Actions
Pattern Inventories
The Cycle Index of a Group
Polya’s Counting Theorem: Statement and Examples
Polya’s Counting Theorem: The Proof
Counting Simple Graphs

Dirichlet’s Pigeonhole Principle
The Origin of the Principle
The Pigeonhole Principle
More Applications of the Pigeonhole Principle

Ramsey Theory
What Is Ramsey’s Theorem?
Three Lovely Theorems
Graphs of Many Colors
Euclidean Ramsey Theory

Rook Polynomials and Matchings
How Rook Polynomials Are Defined
Matchings and Marriages

Solutions to the A Exercises

Books for Further Reading

Index