Bijective Combinatorics

Nicholas A. Loehr teaches in the Department of Mathematics at Virginia Tech. His research interests include enumerative and algebraic combinatorics; symmetric and quasisymmetric functions; integer partitions, lattice paths, parking functions, and tableaux; bijective methods; and algorithm analysis.

Introduction





Basic Counting
Review of Set Theory
Sum Rule
Product Rule
Words, Permutations, and Subsets
Functions
Bijections, Cardinality, and Counting
Subsets, Binary Words, and Compositions
Subsets of a Fixed Size
Anagrams
Lattice Paths
Multisets
Probability
Games of Chance
Conditional Probability and Independence





Combinatorial Identities and Recursions
Generalized Distributive Law
Multinomial and Binomial Theorems
Combinatorial Proofs
Recursions
Recursions for Multisets and Anagrams
Recursions for Lattice Paths
Catalan Recursions
Integer Partitions
Set Partitions
Surjections
Stirling Numbers and Rook Theory
Linear Algebra Review
Stirling Numbers and Polynomials
Combinatorial Proofs of Polynomial Identities





Counting Problems in Graph Theory
Graphs and Digraphs
Walks and Matrices
DAG’s and Nilpotent Matrices
Vertex Degrees
Functional Digraphs
Cycle Structure of Permutations
Counting Rooted Trees
Connectedness and Components
Forests
Trees
Counting Trees
Pruning Maps
Ordered Trees and Terms
Ordered Forests and Lists of Terms
Graph Coloring
Spanning Trees
Matrix-Tree Theorem
Eulerian Tours





Inclusion-Exclusion and Related Techniques
Involutions
The Inclusion-Exclusion Formula
More Proofs of Inclusion-Exclusion
Applications of the Inclusion-Exclusion Formula
Derangements
Coefficients of Chromatic Polynomials
Classical Möbius Inversion
Partially Ordered Sets
Möbius Inversion for Posets
Product Posets





Ranking and Unranking
Ranking, Unranking, and Related Problems
Bijective Sum Rule
Bijective Product Rule
Ranking Words
Ranking Permutations
Ranking Subsets
Ranking Anagrams
Ranking Integer Partitions
Ranking Set Partitions
Ranking Card Hands
Ranking Dyck Paths
Ranking Trees
Successors and Predecessors
Random Selection





Counting Weighted Objects
Weighted Sets
Inversions
Weight-Preserving Bijections
Sum and Product Rules for Weighted Sets
Inversions and Quantum Factorials
Descents and Major Index
Quantum Binomial Coefficients
Quantum Multinomial Coefficients
Foata’s Map
Quantum Catalan Numbers





Formal Power Series
The Ring of Formal Power Series
Finite Products and Powers of Formal Series
Formal Polynomials
Order of Formal Power Series
Formal Limits, Infinite Sums, and Infinite Products
Multiplicative Inverses in K[x] and K[[x]]
Formal Laurent Series
Formal Derivatives
Composition of Polynomials
Composition of Formal Power Series
Generalized Binomial Expansion
Generalized Powers of Formal Series
Partial Fraction Expansions
Application to Recursions
Formal Exponentiation and Formal Logarithms
Multivariable Polynomials and Formal Series





The Combinatorics of Formal Power Series
Sum Rule for Infinite Weighted Sets
Product Rule for Infinite Weighted Sets
Generating Functions for Trees
Compositional Inversion Formulas
Generating Functions for Partitions
Partition Bijections
Euler’s Pentagonal Number Theorem
Stirling Numbers of the First Kind
Stirling Numbers of the Second Kind
The Exponential Formula





Permutations and Group Actions
Definition and Examples of Groups
Basic Properties of Groups
Notation for Permutations
Inversions and Sign
Determinants
Multilinearity and Laplace Expansions
Cauchy-Binet Formula
Subgroups
Automorphism Groups of Graphs
Group Homomorphisms
Group Actions
Permutation Representations
Stable Subsets and Orbits
Cosets
The Size of an Orbit
Conjugacy Classes in Sn
Applications of the Orbit Size Formula
The Number of Orbits
Pólya’s Formula





Tableaux and Symmetric Polynomials
Partition Diagrams and Skew Shapes
Tableaux
Schur Polynomials
Symmetric Polynomials
Homogeneous Symmetric Polynomials
Symmetry of Schur Polynomials
Orderings on Partitions
Schur Bases
Tableau Insertion
Reverse Insertion
Bumping Comparison Theorem
Pieri Rules
Schur Expansion of hα
Schur Expansion of eα
Algebraic Independence
Power-Sum Symmetric Polynomials
Relations between e’s and h’s
Generating Functions for e’s and h’s
Relations between p’s, e’s, and h’s
Power-Sum Expansion of hn and en
The Involution ω
Permutations and Tableaux
Words and Tableaux
Matrices and Tableaux
Cauchy Identities
Dual Bases


Abaci and Antisymmetric Polynomials
Abaci and Integer Partitions
Jacobi Triple Product Identity
Ribbons and k-Cores
k-Quotients and Hooks
Antisymmetric Polynomials
Labeled Abaci
Pieri Rule for pk
Pieri Rule for ek
Pieri Rule for hk
Antisymmetric Polynomials and Schur Polynomials
Rim-Hook Tableaux
Abaci and Tableaux
Skew Schur Polynomials
Jacobi-Trudi Formulas
Inverse Kostka Matrix
Schur Expansion of Skew Schur Polynomials
Products of Schur Polynomials


Additional Topics
Cyclic Shifting of Paths
Chung-Feller Theorem
Rook-Equivalence of Ferrers Boards
Parking Functions
Parking Functions and Trees
Möbius Inversion and Field Theory
Quantum Binomial Coefficients and Subspaces
Tangent and Secant Numbers
Tournaments and the Vandermonde Determinant
Hook-Length Formula
Knuth Equivalence
Pfaffians and Perfect Matchings
Domino Tilings of Rectangles


Answers and Hints to Selected Exercises


Bibliography


Index


A Summary and Exercises appear at the end of each chapter.