Bijective Combinatorics
Purchasing Options
Features
- Presents a readable yet rigorous exposition of enumerative combinatorics
- Emphasizes bijective methods and combinatorial proofs
- Requires minimal mathematical prerequisites
- Includes a careful treatment of ranking, unranking, and successor algorithms
- Provides detailed coverage of algebraic topics, such as formal power series, group actions, and symmetric polynomials, from a combinatorial viewpoint
- Contains numerous worked examples and applications as well as nearly 1,000 exercises, ranging in difficulty from routine verifications to unsolved problems
- Offers solutions, hints, or partial answers to many of the exercises at the end of the book
Errata and other pertinent information are available on the book’s website
Summary
Bijective proofs are some of the most elegant and powerful techniques in all of mathematics. Suitable for readers without prior background in algebra or combinatorics, Bijective Combinatorics presents a general introduction to enumerative and algebraic combinatorics that emphasizes bijective methods.
The text systematically develops the mathematical tools, such as basic counting rules, recursions, inclusion-exclusion techniques, generating functions, bijective proofs, and linear-algebraic methods, needed to solve enumeration problems. These tools are used to analyze many combinatorial structures, including words, permutations, subsets, functions, compositions, integer partitions, graphs, trees, lattice paths, multisets, rook placements, set partitions, Eulerian tours, derangements, posets, tilings, and abaci. The book also delves into algebraic aspects of combinatorics, offering detailed treatments of formal power series, symmetric groups, group actions, symmetric polynomials, determinants, and the combinatorial calculus of tableaux. Each chapter includes summaries and extensive problem sets that review and reinforce the material.
Lucid, engaging, yet fully rigorous, this text describes a host of combinatorial techniques to help solve complicated enumeration problems. It covers the basic principles of enumeration, giving due attention to the role of bijective proofs in enumeration theory.
Table of Contents
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.
Author Bio(s)
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.
Editorial Reviews
This textbook, aimed at beginning graduate students, is the first to survey the subject emphasizing the role of bijections. … The final chapter contains a potpourri of delightful results … The exposition is careful and deliberate, and leaves no stone unturned … a welcome addition to the literature and a very nice book.
—David Callan, Mathematical Reviews, 2012d
A rule I have found to be true is that any book claiming to be suitable for beginners and yet leading to the frontiers of unsolved research problems does neither well. This book is the exception to that rule. … I found this book engaging. The proofs are very clear, and in many cases several proofs are offered. … This book could serve several purposes. By focusing on the first half of the book, it could be an excellent choice for a first course in combinatorics for senior undergraduates. By selecting topics and/or moving quickly, it could work well for a more mature audience. … it also makes a great reference for people who use combinatorics but are not specialists. … This is a very nice book that deserves serious consideration.
—Peter Rabinovitch, MAA Reviews, September 2011
This book is a comprehensive treatment of the combinatorics of counting … The book would be suitable for advanced undergraduates or as a graduate text. It would also be a good book for a computer scientist who wants to learn about enumeration. The book begins with an enchanting introductory chapter. It details a series of interesting motivational problems … The book is clearly written and packed with examples and problems (it provides answers and hints to selected problems at the end). The organization is superior, with helpful tables of notation and definitions at the end of each chapter, along with a point-by-point summary of the chief topics. … the book is an excellent one, and is a comprehensive and welcome addition to the area.
—Angele M. Hamel, Computing Reviews, August 2011
