# Book:Alan Tucker/Applied Combinatorics/Fifth Edition

## Alan Tucker: Applied Combinatorics (5th Edition)

Published $\text {2007}$, Wiley

ISBN 978-0471438090

### Contents

PRELUDE
PART ONE: GRAPH THEORY
CHAPTER 1: ELEMENTS OF GRAPH THEORY
1.1 Graph Models
1.2 Isomorphism
1.3 Edge Counting
1.4 Planar Graphs
1.5 Summary and References
Supplementary Exercises
CHAPTER 2: COVERING CIRCUITS AND GRAPH COLORING
2.1 Euler Cycles
2.2 Hamilton Circuits
2.3 Graph Coloring
2.4 Coloring Theorems
2.5 Summary and References
Supplement: Graph Model for Instant Insanity
Supplement: Exercises
CHAPTER 3: TREES AND SEARCHING
3.1 Properties of Trees
3.2 Search Trees and Spanning Trees
3.3 The Traveling Salesperson Problem
3.4 Tree Analysis of Sorting Problems
3.5 Summary and References
CHAPTER 4: NETWORK ALGORITHMS
4.1 Shortest Paths
4.2 Minimal Spanning Trees
4.3 Network Flows
4.4 Algorithmic Matching
4.5 The Transportation Problem
4.6 Summary and References
PART TWO: ENUMERATION
CHAPTER 5: GENERAL COUNTING METHODS FOR ARRANGEMENTS AND SELECTIONS
5.1 Basic Counting Principles
5.2 Simple Arrangements and Selections
5.3 Arrangements and Selections with Repetitions
5.4 Distributions
5.5 Binomial Identities
5.6 Summary and References
Supplement: Selected Solutions to Problems in Chapter 5
CHAPTER 6: GENERATING FUNCTIONS
6.1 Generating Function Models
6.2 Calculating Coefficients of Generating Functions
6.3 Partitions
6.4 Exponential Generating Functions
6.5 A Summation Method
6.6 Summary and References
CHAPTER 7: RECURRENCE RELATIONS
7.1 Recurrence Relation Models
7.2 Divide-and-Conquer Relations
7.3 Solution of Linear Recurrence Relations
7.4 Solution of Inhomogeneous Recurrence Relations
7.5 Solutions with Generating Functions
7.6 Summary and References
CHAPTER 8: INCLUSION-EXCLUSION
8.1 Counting with Venn Diagrams
8.2 Inclusion-Exclusion Formula
8.3 Restricted Positions and Rook Polynomials
8.4 Summary and Reference
CHAPTER 9: POLYA'S ENUMERATION FORMULA
9.1 Equivalence and Symmetry Groups
9.2 Burnside's Theorem
9.3 The Cycle Index
9.4 Polya's Formula
9.5 Summary and References
CHAPTER 10: COMPUTER SCIENCE APPROACHES TO ENUMERATION
10.1 Generating Permutations and Combinations and Programming Projects
10.2 Formal Languages and Grammars
10.3 Finite-State Machines
10.4 Summary and References
CHAPTER 11: GAMES WITH GRAPHS
11.1 Progressively Finite Games
11.2 Nim-Type Games
11.3 Summary and References
APPENDIX
A.1 Set Theory
A.2 Mathematical Induction
A.3 A Little Probability
A.4 The Pigeonhole Principle
A.5 Computational Complexity and NP-Completeness
GLOSSARY OF COUNTING AND GRAPH THEORY TERMS
BIBLIOGRAPHY
SOLUTIONS TO ODD-NUMBERED PROBLEMS
INDEX