Publisher:

Chapman & Hall/CRC

Number of Pages:

590

Price:

99.95

ISBN:

9781439848845

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.

Date Received:

Thursday, June 2, 2011

Reviewable:

Yes

Series:

Discrete Mathematics and Its Applications

Publication Date:

2011

Format:

Hardcover

Audience:

Category:

Textbook

Peter Rabinovitch

09/22/2011

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

Publish Book:

Modify Date:

Wednesday, February 29, 2012

- Log in to post comments