You are here

Bijective Combinatorics

Nicholas A. Loehr
Publisher: 
Chapman & Hall/CRC
Publication Date: 
2011
Number of Pages: 
590
Format: 
Hardcover
Series: 
Discrete Mathematics and Its Applications
Price: 
99.95
ISBN: 
9781439848845
Category: 
Textbook
BLL Rating: 

The Basic Library List Committee suggests that undergraduate mathematics libraries consider this book for acquisition.

[Reviewed by
Peter Rabinovitch
, on
09/22/2011
]

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.

A glance at the table of contents reveals many of the standard combinatorics topics. As the title implies, they are generally explored via bijections. As a user of combinatorics, rather than a dyed in the wool combinatorialist, I find bijections to be the central core of the subject and so I found this book engaging.

The proofs are very clear, and in many cases several proofs are offered. For example, there may be an algebraic proof of an identity, followed by a bijective proof.

This book could serve several purposes. By focussing on the first half of the book, it could be an excellent choice for a first course in cominatorics for senior undergraduates. By selecting topics and/or moving quickly, it could work well for a more mature audience. The book is at a higher level than Stanton & White, but lower than Stanley, thus it also makes a great reference for people who use combinatorics but are not specialists.

There are many exercises. The back cover claims nearly 1000, and although I didn’t count them, I have no reason to doubt this claim. Some are very simple, and some are hard — the back cover claims some are unsolved. Many of the exercises are discussed in an appendix, ranging in detail from mere hints to “draw a diagram” to full but terse solutions. Because there are so many exercises, and because the level of detail of the provided solutions varies so much, an instructor using this text could easily find appropriate problems for assignment for courses of various levels of sophistication.

There are few obvious typos.

On the negative side, the book’s web site is empty, and the author uses “quantum numbers” and “quantum binomial coefficients” etc. rather than the more common “q numbers” and “q binomial coefficients.”

This is a very nice book that deserves serious consideration.


Peter Rabinovitch is a Systems Architect at Research in Motion, and a PhD student in probability. He’s currently thinking about applications of Mallows permutations.

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