##
**Enumerative combinatorics. Vol. I.**
*(English)*
Zbl 0608.05001

The Wadsworth & Brooks/Cole Mathematics Series. Monterey, California: Wadsworth & Brooks/Cole Advanced Books & Software. xi, 306 p. $ 42.95 (1986).

This extraordinary successful book is an excellent introduction to enumerative combinatorics on the one hand, at the same time, however, it is a monograph comprising a number of the latest results on the other. It may be used as a graduate-level introduction to the combinatorics, however, even professional combinatorialists will find many interesting parts therein. Last, but not least, the book will be useful and inspiring for mathematicians outside combinatorics whose work requires them to solve a combinatorial problem.

The text is organized into four chapters and one appendix. Chapter headings: (1) What is enumerative combinatorics? (2) Sieve methods. (3) Partially ordered sets. (4) Rational generating functions. Appendix: Graph theory terminology. Each chapter has its own list of references. In the Notes at the end of each chapter the author presents a short history of problems and comments on main ideas and techniques. Every chapter is submitted with some tens of examples, exercises and problems. (The extraordinary role of these parts will be mentioned later.)

The first chapter is an excellent survey of the basic problems of enumerative combinatorics, the second one contains a survey of basic combinatorial methods and techniques (Inclusion - Exclusion, Ferrers boards, involutions and others). The heart of the book lies in the third and fourth chapter. In the third chapter, the author studies posets, lattices, distributive lattices, the incidence algebra of a locally finite poset, the Möbius inversion formula, techniques for computing Möbius functions, zeta polynomials, rank selection, Eulerian posets, binomial posets and generating functions and others. The fourth chapter deals with rational power series in one variable, \(P\)-partitions (a \(P\)-partition of a finite poset \(P\) of cardinality \(p\) is an order-reversing map \(f: P\to \mathbb N\) satisfying \(\sum f(i)=n)\), linear homogeneous diophantine equations and the transfer-matrix methods.

Quite an extraordinary role in this book is played by exercises at the end of each chapter. They are arranged from the easier exercises, suitable for students using the book as a text, up to very difficult exercises and unsolved problems. (The level of difficulty is marked at every exercise.) These exercises serve as an entry into areas that are not directly covered by the text, extend the frame of the book and comprise a series of the newest results. Examples, chosen appropriately from other branches of mathematics (topology, computer science, algebra, functions of complex variables, and others), demonstrate the extent of applications of the studied theory. First of all the problems in the third chapter will be the most useful part of the book for many readers. (The author presents 81 examples of non-trivial and many times not expected applications in this chapter.) Solutions or references to solutions are provided for all of the exercises.

The study of this book was a real pleasure for the reviewer.

The text is organized into four chapters and one appendix. Chapter headings: (1) What is enumerative combinatorics? (2) Sieve methods. (3) Partially ordered sets. (4) Rational generating functions. Appendix: Graph theory terminology. Each chapter has its own list of references. In the Notes at the end of each chapter the author presents a short history of problems and comments on main ideas and techniques. Every chapter is submitted with some tens of examples, exercises and problems. (The extraordinary role of these parts will be mentioned later.)

The first chapter is an excellent survey of the basic problems of enumerative combinatorics, the second one contains a survey of basic combinatorial methods and techniques (Inclusion - Exclusion, Ferrers boards, involutions and others). The heart of the book lies in the third and fourth chapter. In the third chapter, the author studies posets, lattices, distributive lattices, the incidence algebra of a locally finite poset, the Möbius inversion formula, techniques for computing Möbius functions, zeta polynomials, rank selection, Eulerian posets, binomial posets and generating functions and others. The fourth chapter deals with rational power series in one variable, \(P\)-partitions (a \(P\)-partition of a finite poset \(P\) of cardinality \(p\) is an order-reversing map \(f: P\to \mathbb N\) satisfying \(\sum f(i)=n)\), linear homogeneous diophantine equations and the transfer-matrix methods.

Quite an extraordinary role in this book is played by exercises at the end of each chapter. They are arranged from the easier exercises, suitable for students using the book as a text, up to very difficult exercises and unsolved problems. (The level of difficulty is marked at every exercise.) These exercises serve as an entry into areas that are not directly covered by the text, extend the frame of the book and comprise a series of the newest results. Examples, chosen appropriately from other branches of mathematics (topology, computer science, algebra, functions of complex variables, and others), demonstrate the extent of applications of the studied theory. First of all the problems in the third chapter will be the most useful part of the book for many readers. (The author presents 81 examples of non-trivial and many times not expected applications in this chapter.) Solutions or references to solutions are provided for all of the exercises.

The study of this book was a real pleasure for the reviewer.

Reviewer: Eduard Fuchs (Brno)

### MSC:

05-02 | Research exposition (monographs, survey articles) pertaining to combinatorics |

05A15 | Exact enumeration problems, generating functions |

06A06 | Partial orders, general |

06B05 | Structure theory of lattices |

06D05 | Structure and representation theory of distributive lattices |

### Keywords:

enumerative combinatorics; sieve methods; Partially ordered sets; rational generating functions; graph theory terminology### Online Encyclopedia of Integer Sequences:

Number of cyclic permutations of [n] with no i -> i+1 (mod n).Numerators of continued fraction convergents to sqrt(2).

a(n) = Sum_{k=0..n} k!(n-k)!.

Expansion of (2 + 2*x - 3*x^2) / (1 - 2*x - x^2 + x^3).

Number of permutations (p1,...,pn) such that 1 <= |pk - k| <= 2 for all k.

Number of standard permutations of [ a_1..a_n b_1..b_n ] (b_i is not immediately followed by a_i, for all i).

Number of ways to place 3 nonattacking queens on an n X n board.

Number of letters in n-th Catalan number.

Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n, having k long ascents (i.e., ascents of length at least 2). Rows are of length 1,1,2,2,3,3,... .

From enumerating paths in the plane.

Array T(m,n) read by antidiagonals: number of domino tilings (or dimer tilings) of the m X n grid (or m X n rectangle), for m>=1, n>=1.

Number of linear extensions of the divisor lattice of n.

Dimension of the space spanned by the symmetric functions L_lambda of Gessel and Reutenauer, where lambda ranges over all partitions of n.

Minimal index of a Stanley antimagic square of order n consisting of distinct primes.

Square array A(n,k), n>=0, k>=0, read by antidiagonals: A(n,k) = sum of the k-th powers of multinomials M(n; mu), where mu ranges over all compositions of n.

Square array read by descending antidiagonals. T(n,k) is the number of ways to separate the columns of an ordered pair of n-permutations (that have been written as a 2 X n array, one atop the other) into k cells so that no cell has a column rise. For n >= 0, k >= 0.