This textbook introduces enumerative combinatorics through the framework of formal languages and bijections. By starting with elementary operations on words and languages, the authors paint an insightful, unified picture for readers entering the field. Numerous concrete examples and illustrative metaphors motivate the theory throughout, while the overall approach illuminates the important connections between discrete mathematics and theoretical computer science.
Beginning with the basics of formal languages, the first chapter quickly establishes a common setting for modeling and counting classical combinatorial objects and constructing bijective proofs. From here, topics are modular and offer substantial flexibility when designing a course. Chapters on generating functions and partitions build further fundamental tools for enumeration and include applications such as a combinatorial proof of the Lagrange inversion formula. Connections to linear algebra emerge in chapters studying Cayley trees, determinantal formulas, and the combinatorics that lie behind the classical Cayley–Hamilton theorem. The remaining chapters range across the Inclusion-Exclusion Principle, graph theory and coloring, exponential structures, matching and distinct representatives, with each topic opening many doors to further study. Generous exercise sets complement all chapters, and miscellaneous sections explore additional applications.
Lessons in Enumerative Combinatorics captures the authors' distinctive style and flair for introducing newcomers to combinatorics. The conversational yet rigorous presentation suits students in mathematics and computer science at the graduate, or advanced undergraduate level. Knowledge of single-variable calculus and the basics of discrete mathematics is assumed; familiarity with linear algebra will enhance the study of certain chapters.
Author(s): Ömer Eğecioğlu, Adriano M. Garsia
Series: Graduate Texts in Mathematics, 290
Publisher: Springer
Year: 2021
Language: English
Pages: 495
City: Cham
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
