Website for Bijective Combinatorics by Nick Loehr
Bijective Combinatorics presents a general introduction
to enumerative combinatorics that emphasizes bijective methods.
The text contains a systematic development of the mathematical
tools needed to solve combinatorial problems: basic counting rules,
recursions, inclusion-exclusion formulas, generating functions,
bijective proofs, and linear-algebraic techniques. 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.
Later chapters delve into some of the algebraic aspects of
combinatorics, including detailed treatments of formal power series,
symmetric groups, group actions, symmetric polynomials, determinants,
and the combinatorial calculus of tableaux.
Order the book
Website for CRC Press.
Reader Feedback and Errata
If you have comments about the book or have discovered any errors,
please contact the author by e-mail (nloehr at vt dot edu).
List of errata
(last updated 1/11/2012).
Synopsis of Book
Chapter 1: Basic Counting.
The text begins by stating and proving the most fundamental counting
rules, including the sum rule and the product rule. These rules are
used to enumerate combinatorial structures such as words,
permutations, subsets, functions, anagrams, and lattice paths.
Bijections and bijective proofs are introduced at an early stage
and are then applied to help count compositions, multisets,
and Dyck paths. The end of the chapter discusses applications
of combinatorics in elementary probability theory.
Chapter 2: Combinatorial Identities and Recursions.
The chapter opens with a discussion of the generalized distributive law,
which allows one to simplify a product of sums in an arbitrary ring.
This law leads to proofs of the binomial and multinomial theorems
(in both commutative and non-commutative rings) that illuminate
the connections to combinatorics on words. Next, recursions are
introduced as a powerful tool for enumerating discrete
structures. Recursions are used to analyze multisets, anagrams,
lattice paths, integer partitions, set partitions, and surjections,
as well as families of objects counted by the Catalan numbers.
We study Stirling numbers and their connections to set partitions
and rook theory, which leads to an analysis of the transition matrices
between different bases for the vector space of polynomials in one
variable. A final section describes how combinatorial arguments can
be used to prove certain polynomial identities.
Chapter 3: Counting Problems in Graph Theory.
This chapter contains an introduction to the vast subject of graph
theory that concentrates on enumerative issues. After some initial
definitions, we show that powers of the adjacency matrix contain
information about the number of walks in a graph. The connection
between directed acyclic graphs (DAG's) and nilpotent matrices
is explained. We discuss the graph-theoretic concepts of vertex degrees,
forests, trees, leaves, rooted trees, connectedness, components, and
functional digraphs. The representation of permutations as digraphs that
are disjoint unions of cycles leads to a combinatorial interpretation for
the Stirling numbers of the first kind. Trees and rooted trees are enumerated
by bijections to certain sets of functional digraphs. Pruning maps
(also called Prüfer codes) are introduced to give a refinement of this
result that counts trees with specified vertex degrees. We then
study terms, lists of terms, ordered trees, and ordered forests,
which are enumerated with the aid of the famous "cycle lemma."
Next we consider proper colorings of graphs, chromatic polynomials,
and chromatic numbers. A recursion based on deleting and contracting
a given edge is used to calculate chromatic polynomials. A similar
recursion then arises in the enumeration of spanning trees of a graph.
This leads to a proof of the matrix-tree theorem in which a
recursion for rooted spanning trees is related to multilinearity properties
of the determinant of the truncated Laplacian matrix. Finally,
aided by these results, we address the existence and enumeration
of Eulerian tours in a balanced, connected digraph.
Chapter 4: Inclusion-Exclusion and Related Techniques.
This chapter begins with a discussion of involutions,
which are bijections on sets of signed objects. Various
forms of the inclusion-exclusion formula are presented.
We give several proofs of this formula, illustrating a mixture
of algebraic, combinatorial, and bijective methods.
We then apply inclusion-exclusion techniques to obtain formulas
for surjections, Stirling numbers, Euler's φ-function,
derangements, the coefficients in chromatic polynomials, and
objects avoiding specified conditions. The chapter ends with
a brief treatment of the classical (number-theoretic) Möbius
inversion formula and its generalization to Möbius functions on
posets, leading to an interpretation of inclusion-exclusion
as a Möbius inversion result for Boolean posets.
Chapter 5: Ranking and Unranking.
This chapter studies algorithms for ranking and unranking
combinatorial objects. The goal is to compute explicit
bijections that map objects
in a given finite set to positions on a list, and vice versa.
We present systematic techniques for solving such problems
based on bijective versions of the sum and product rules.
These rules are used to rank and unrank words, permutations,
subsets, anagrams, integer partitions, set partitions, card hands,
Dyck paths, and trees. Two final sections consider the related
problems of finding successors, finding predecessors, and
randomly selecting an object from a given collection.
The algorithms in this chapter provide useful building blocks
for computer simulations and programs that must loop over large
sets of discrete structures.
Chapter 6: Counting Weighted Objects.
This chapter introduces the idea of a generating function
as a way to count sets of weighted objects. For simplicity,
we initially consider only finite weighted sets. Weighted versions
of the sum rule, product rule, and bijection rule are presented.
This leads to a discussion of quantum factorials,
quantum binomial coefficients (also called q-binomial coefficients),
quantum multinomial coefficients, and the associated statistics
on permutations and words (inversions and major index).
An optional section describes Foata's bijective proof of the
equidistribution of inv and maj on the set of anagrams of a
given word. Another optional section considers q-analogues of
Catalan numbers obtained by weighting Dyck words by inversions
or by major index.
Chapter 7: Formal Power Series.
To extend the notion of a generating function to apply to
infinite weighted sets, one has two choices: use convergent
power series of a real (or complex) variable, or use formal
power series. We elect to use formal power series, and this
chapter gives a detailed account of the basic algebraic
properties of such series. We define the ring
of formal power series K[[x]] for any field K of characteristic
zero, as well as the subring K[x] of formal polynomials.
We proceed to give a thorough and rigorous exposition
of degree, order, evaluation homomorphisms, formal limits,
formal infinite sums of series, formal infinite products of series,
convergence criteria, units in K[x] and K[[x]], formal
geometric series, formal Laurent series, formal derivatives,
composition of formal series, the formal chain rule, compositional
inverses, the generalized binomial theorem, powers of series,
n'th roots of series, partial fractions, formal exponentiation,
formal logarithms, and extensions to multivariable polynomials
and series. A recurring theme is that many familiar facts from
calculus, such as exp(x+y)=exp(x)exp(y),
can be proved (at least at the
formal level) by elementary algebraic and combinatorial manipulations
of coefficients in power series. The chapter also includes an
application of formal series and partial fractions to the problem
of solving recursions. Beginning readers can readily skip or skim
this chapter and proceed to the combinatorial aspects of formal
power series contained in Chapter 8.
Chapter 8: Combinatorial Power Series.
This chapter applies the machinery of formal power series
(as developed in Chapter 7) to solve combinatorial problems
involving the enumeration of infinite weighted sets. First
we develop versions of the sum rule and product rule for
infinite sets. Formal power series are then used to enumerate
binary trees, full binary trees, and ordered trees. An initial
algebraic solution based on the formal quadratic formula leads
to the development of bijections linking these classes of trees.
We continue with a combinatorial account of Lagrange's formula
for computing compositional inverses, based on the enumeration
of terms in Chapter 3. The next few sections give a brief
introduction to the vast subject of generating functions
and bijections for integer partitions. We give three proofs
that the number of partitions of n into odd parts equals
the number of partitions of n into distinct parts — one based
on formal power series, one based on a bijection of Sylvester,
and one based on a bijection of Glaisher. Next we present
Franklin's beautiful involution proving Euler's pentagonal number
theorem, which gives the expansion of the infinite product
and leads to an amazing recursion for the partition function p(n).
The chapter closes with an analysis of generating functions for
Stirling numbers and a proof of the exponential formula, which
illuminates the combinatorial meaning of the exponential of a formal series.
Chapter 9: Permutations and Group Actions.
This chapter contains an account of group theory emphasizing those
aspects most pertinent to combinatorial problems: symmetric groups,
group actions, the orbit-counting theorem (often called Burnside's lemma),
and Pólya's extension of this theorem to weighted sets. After
giving basic definitions and examples, the symmetric groups
are investigated in some detail. We describe the one-line form and
cycle notation for permutations. Inversions are used to define
the sign of a permutation and to prove that sgn is a group homomorphism.
The next few sections offer an optional foray into the theory of determinants,
featuring combinatorial proofs of identities such as the Cauchy-Binet formula,
Laplace expansions, and the adjoint formula for the inverse of a matrix.
We then turn to subgroups and their properties. The automorphism group of a
graph is introduced as a precise way to measure the symmetry in a graph;
as examples, we compute the automorphism groups of cycles (directed and
graphs modeling chessboards, and cubes. Subsequent sections cover group
homomorphisms, group actions, permutation representations, Cayley's theorem,
orbits of an action, stabilizer subgroups, conjugacy classes, cosets,
centralizers, normalizers, and Lagrange's theorem. The Orbit Size Theorem,
which says that the size of the orbit of x equals the index of the
stabilizer subgroup of x, is applied to give combinatorial proofs of
Fermat's little theorem,
Cauchy's theorem, Lucas' congruence for binomial coefficients modulo a prime,
and the first Sylow theorem. Finally, we prove the orbit-counting theorem
and Pólya's theorem and show how these results can be used in
counting problems where symmetries must be taken into account.
Chapter 10: Tableaux and Symmetric Polynomials.
The theory of symmetric polynomials, with its close-knit relation to
tableau combinatorics, provides an ideal venue for illustrating the
algebraic significance of bijections and enumerative ideas. This chapter
gives a highly combinatorial account of the basic facts of this theory.
The Schur polynomials and skew Schur polynomials are defined as
generating functions for semistandard tableaux, and these polynomials are
shown to be symmetric via content-modifying bijections on tableaux.
After defining other commonly used symmetric polynomials —
the monomial symmetric polynomials, the elementary symmetric
polynomials, the complete symmetric polynomials,
and the power-sum symmetric polynomials — we begin to
develop the fundamental algebraic properties of these objects.
A mixture of combinatorics and matrix algebra is used to show that
the Schur polynomials (as well as other symmetric polynomials just mentioned)
form a basis for the vector space of symmetric polynomials. Suitable
recursions establish the algebraic independence of the elementary
(resp. complete, power-sum) symmetric polynomials.
Further topics include the dominance partial ordering
of partitions, Kostka numbers, Schensted's tableau insertion algorithm,
reverse insertion, the bumping comparison theorem, the Pieri rules,
the Schur expansions of complete and elementary symmetric polynomials,
the power-sum expansions of hn
and en, the involution ω,
the Cauchy identities, dual bases, and the Hall scalar product.
The chapter concludes with an exposition of different versions
of the RSK algorithm, which map permutations, words, and matrices
to pairs of Young tableaux satisfying certain conditions. Shadow
diagrams are used to show that if a given permutation maps to the
pair of tableaux (P,Q) under RSK, then the inverse permutation
maps to (Q,P).
Chapter 11: Abaci and Antisymmetric Polynomials.
The first part of the chapter employs combinatorial objects called
abaci to prove interesting facts about integer partitions. Bijections
on suitably weighted abaci furnish a proof of the Jacobi triple product
identity. We then discuss k-cores and k-quotients of partitions,
which generalize the operation of dividing an ordinary integer by k.
The model of a k-runner abacus proves the uniqueness of the
of a partition and gives one way to compute the k-quotients. We also
give another interpretation of k-quotients in terms of the hooks of the
diagram of a partition. The remainder of the chapter continues the
study of symmetric polynomials begun in Chapter 10. The central algebraic
objects are now antisymmetric polynomials, which can be converted
to symmetric polynomials by dividing by the Vandermonde determinant.
The central combinatorial objects are
labeled abaci, which model monomial antisymmetric polynomials.
Aided by these abaci, we give combinatorial proofs of the Pieri rules,
the classical formula for Schur
polynomials as a quotient of determinants, the Schur expansion of
power-sum symmetric polynomials,
the power-sum expansion of skew Schur polynomials,
the Jacobi-Trudi formulas, a combinatorial interpretation of the
inverse Kostka matrix, and two versions of the Littlewood-Richardson rule
(which describe the Schur expansions of skew Schur polynomials
and the product of two Schur polynomials).
Chapter 12: Additional Topics.
The final chapter consists of independent sections covering
optional topics that complement material in the main text.
These topics include: the use of cyclic shifting bijections
in lattice path enumeration; a bijective proof of the Chung-Feller theorem
on the uniform distribution of flaws in square lattice paths;
the multiset criterion for deciding when two Ferrers boards
are rook-equivalent; the definition and enumeration of parking
functions; bijections connecting parking functions and trees;
the use of counting arguments to prove theorems in field theory,
including the enumeration of irreducible polynomials
via Möbius inversion; the linear-algebraic meaning of q-binomial
coefficients; the combinatorial interpretation for the coefficients
in the Maclaurin power series for tan(x) and sec(x);
tournaments and a combinatorial method for evaluating Vandermonde
determinants; a probabilistic proof of the hook-length formula
for the number of standard Young tableaux; Knuth equivalence and
longest increasing subsequences of words; Pfaffians and their
relation to perfect matchings of graphs; and the famous exact
formula for the number of ways to tile a rectangular board with dominos.
This page was last updated on May 2016.