- 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*

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.

**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 *S _{n}*

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

Algebraic Independence

Power-Sum Symmetric Polynomials

Relations between

Generating Functions for

Relations between

Power-Sum Expansion of

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

Antisymmetric Polynomials

Labeled Abaci

Pieri Rule for

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.*

**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.

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