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

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
 ∞ 

i = 1
(1-xi) 
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 undirected), 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 k-core 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.

Reviews


This page was last updated on 6 May 2013.