Lessons in Enumerative Combinatorics

Foreword
Preface
Contents
1 Basic Combinatorial Structures
	1.1 Introduction
	1.2 Languages
		1.2.1 Length
		1.2.2 Concatenation
		1.2.3 The Empty Word
		1.2.4 Initial Segments
		1.2.5  A* and A+
		1.2.6 Lexicographic Order
		1.2.7 Set theoretical Notation
		1.2.8 Listing Series and Algebraic Operations
	1.3 The 2-Letter Alphabet, Sets, and Lattice Paths
		1.3.1 Sets
		1.3.2 Lattice Paths
	1.4 The Dyck Language, Ballot Sequences, Nested Parentheses, and 2-Rowed Young Tableaux
	1.5 Injective Words
	1.6 Increasing Words
	1.7 Set Partitions and Restricted Growth Words
	1.8 Stirling Numbers of the Second Kind
	1.9 Permutations and Stirling Numbers of the First Kind
	1.10 Exercises for Chapter 1
	1.11 Sample Quiz for Chapter 1
2 Partitions and Generating Functions
	2.1 Ferrers Diagrams
	2.2 Generating Functions
	2.3 The Euler Recursion for the Partition Function
	2.4 Inversion Generating Function for Permutations
	2.5 Parity
	2.6 Gaussian Polynomials
	2.7 Miscellaneous Identities
		2.7.1 Durfee Square
		2.7.2 Hook Shapes
		2.7.3 Classifying All Partitions
		2.7.4 Self-Conjugate Partitions
		2.7.5 Partitions with Distinct Parts
		2.7.6 Binary Expansions
		2.7.7 Rogers–Ramanujan Identities
	2.8 Exercises for Chapter 2
	2.9 Sample Quiz for Chapter 2
3 Planar Trees and the Lagrange Inversion Formula
	3.1 Planar Trees
		3.1.1 Depth First Order
		3.1.2 Tree Multiplication
		3.1.3 The Word of a Tree
	3.2 Planar Binary Trees
	3.3 Ternary Trees
	3.4 Lattice Path Representation for Planar Trees
	3.5 Combinatorial Enumeration of Binary Trees
	3.6 A Combinatorial Proof of the Lagrange Inversion Formula
	3.7 Miscellaneous Applications and Examples
		3.7.1 Incomplete Binary Trees
		3.7.2 0-1-2 Trees
		3.7.3 Enumeration of Binary Trees by External Nodes
		3.7.4 The Number of Planar Trees
	3.8 Exercises for Chapter 3
	3.9 Sample Quiz for Chapter 3
4 Cayley Trees
	4.1 Introduction
	4.2 The Monomial and the Word of a Cayley Tree
	4.3 The Prüfer Bijection
	4.4 Enumeration of Cayley Trees and Cayley Forests
	4.5 Functional Digraphs, the Joyal Encoding
	4.6 A Determinantal Formula for Cayley Trees
	4.7 Extensions and Applications
	4.8 Exercises for Chapter 4
	4.9 Sample Quiz for Chapter 4
5 The Cayley–Hamilton Theorem
	5.1 The Cayley–Hamilton Theorem
	5.2 Miscellaneous Applications and Examples
		5.2.1 The Division Method
		5.2.2 The Interpolation Method
		5.2.3 Solutions of Differential Equations
		5.2.4 Solutions of Difference Equations
	5.3 Exercises for Chapter 5
	5.4 Sample Quiz for Chapter 5
6 Exponential Structures and Polynomial Operators
	6.1 More on Partitions and Permutations
	6.2 Exponential Structures
	6.3 The Exponential Formula and Some Applications
	6.4 Polynomial Operators
		6.4.1 The Shift Operator
		6.4.2 The Evaluation Operator
		6.4.3 The Difference Operator
		6.4.4 Applications of the Difference Operator
		6.4.5 Pairs of Polynomial Sequences
		6.4.6 An Application of the Lagrange Inversion Formula
	6.5 Miscellaneous Applications and Examples
		6.5.1 The Mullin–Rota Theory of Polynomial Sequences of Binomial Type
		6.5.2 Permutations with Even Cycles, Involutions Without Fixed Points
		6.5.3 Lagrange Interpolation
	6.6 Exercises for Chapter 6
	6.7 Sample Quiz for Chapter 6
7 The Inclusion-Exclusion Principle
	7.1 A Special Case
	7.2 The General Formulation
	7.3 Two Classical Examples
		7.3.1 Divisibility Properties
		7.3.2 Permutations Without Fixed Points
	7.4 Further Identities
	7.5 Miscellaneous Applications and Examples
		7.5.1 The Ménage Problem
		7.5.2 Rook Numbers and Hit Polynomials
		7.5.3 Rises of Permutations and Ferrers Boards
		7.5.4 Descents and Ascents of Permutations
	7.6 Exercises for Chapter 7
	7.7 Sample Quiz for Chapter 7
8 Graphs, Chromatic Polynomials, and Acyclic Orientations
	8.1 Graphs
	8.2 Chromatic Polynomials
	8.3 Acyclic Orientations
	8.4 The Cartier–Foata Languages
	8.5 Planar Graphs
		8.5.1 Kuratowski's Theorem
		8.5.2 Euler's Formula
	8.6 Miscellaneous Applications and Examples
		8.6.1 Spanning Trees and the Matrix-Tree Theorem
		8.6.2 Computation of Chromatic Polynomials
		8.6.3 Trees
		8.6.4 The Circuit Graphs
		8.6.5 The Wheel Graphs
		8.6.6 A Reduction Rule
		8.6.7 Colorings and Inclusion-Exclusion
		8.6.8 The Platonic Solids
	8.7 Exercises for Chapter 8
	8.8 Sample Quiz for Chapter 8
9 Matching and Distinct Representatives
	9.1 Binary Matrices, Marked Checkerboards, Rook Domains, and Planks
	9.2 The Distinct Representative Theorem
	9.3 Applications
	9.4 The First Available Matching Algorithm
	9.5 Exercises for Chapter 9
	9.6 Sample Quiz for Chapter 9
Reference Books
Bibliography
Index