Enumerative combinatorics. Vol. 1. (English) Zbl 0889.05001
Cambridge Studies in Advanced Mathematics. 49. Cambridge: Cambridge University Press. xi, 325 p. (1997).
[See Zbl 0608.05001 for the first edition published by Wadsworth.]
As the author explains in his introduction: “This book has three intended audiences and serves three different purposes. First, it may be used as a graduate-level introduction to a fascinating area of mathematics \(\dots\). The second intended audience consists of professional combinatorialists, for whom this book could serve as a general reference \(\dots\). Finally, this book may be used by mathematicians outside combinatorics whose work requires them to solve a combinatorial problem.”
The book serves all of these audiences well. The first chapter is a basic introduction to combinatorics and includes the fundamental counting formulas organized as counting functions under various conditions. The second chapter is devoted to a discussion of sieve methods. The remainder of the book consists of two long chapters: Partially ordered sets and Rational generating functions.
The book contains many careful examples and includes a large variety of exercises. The exercises are rated as to difficulty and a complete set of solutions is included. In addition each chapter contains a collection of historical notes and an extensive set of references.
As the author explains in his introduction: “This book has three intended audiences and serves three different purposes. First, it may be used as a graduate-level introduction to a fascinating area of mathematics \(\dots\). The second intended audience consists of professional combinatorialists, for whom this book could serve as a general reference \(\dots\). Finally, this book may be used by mathematicians outside combinatorics whose work requires them to solve a combinatorial problem.”
The book serves all of these audiences well. The first chapter is a basic introduction to combinatorics and includes the fundamental counting formulas organized as counting functions under various conditions. The second chapter is devoted to a discussion of sieve methods. The remainder of the book consists of two long chapters: Partially ordered sets and Rational generating functions.
The book contains many careful examples and includes a large variety of exercises. The exercises are rated as to difficulty and a complete set of solutions is included. In addition each chapter contains a collection of historical notes and an extensive set of references.
Reviewer: J.E.Graver (Syracuse)
MSC:
| 05-02 | Research exposition (monographs, survey articles) pertaining to combinatorics |
| 05A15 | Exact enumeration problems, generating functions |
| 05A16 | Asymptotic enumeration |
| 06A07 | Combinatorics of partially ordered sets |
Keywords:
enumerative combinatorics; partially ordered sets; generating functions; counting; sieve methodsCitations:
Zbl 0608.05001Digital Library of Mathematical Functions:
§26.13 Permutations: Cycle Notation ‣ Properties ‣ Chapter 26 Combinatorial Analysis§26.14(ii) Generating Functions ‣ §26.14 Permutations: Order Notation ‣ Properties ‣ Chapter 26 Combinatorial Analysis
§26.14(i) Definitions ‣ §26.14 Permutations: Order Notation ‣ Properties ‣ Chapter 26 Combinatorial Analysis
§26.15 Permutations: Matrix Notation ‣ Properties ‣ Chapter 26 Combinatorial Analysis
§26.17 The Twelvefold Way ‣ Properties ‣ Chapter 26 Combinatorial Analysis
Example 3 ‣ §26.18 Counting Techniques ‣ Properties ‣ Chapter 26 Combinatorial Analysis
Chapter 26 Combinatorial Analysis
Online Encyclopedia of Integer Sequences:
F(2n) = bisection of Fibonacci sequence: a(n) = 3*a(n-1) - a(n-2).Take every 5th term of Padovan sequence A000931, beginning with the second term.
a(0)=1; a(n) = 2*3^(n-1) for n >= 1.
a(n) = floor(2^|n-1|/2). Or: 1, 0, followed by powers of 2.
Triangle whose (i,j)-th entry is binomial(i,j)*4^(i-j)*3^j.
Number of letters in n-th Catalan number.
Number of decimal digits of A070177(n).
Second binomial transform of F(n+1).
Row T(n,3) of number array A086404.
a(0) = 1, a(n) = Fibonacci(2*n). It has the property that a(n) = 1*a(n-1) + 2*a(n-2) + 3*a(n-3) + 4*a(n-4) + ...
Triangle read by rows: T(n,k) = |s(n,n+1-k)|, where s(n,k) are the signed Stirling numbers of the first kind A008276 (1 <= k <= n; in other words, the unsigned Stirling numbers of the first kind in reverse order).
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.
Dimension of the space spanned by the symmetric functions L_lambda of Gessel and Reutenauer, where lambda ranges over all partitions of n.
Number of set partitions with at most 3 blocks; number of Dyck paths of height at most 4; dimension of space of symmetric polynomials in 3 noncommuting variables.
Number of increasing trees with hills of height 1.
Number of increasing trees with branches of height 1.
Number of chains (totally ordered subsets) in the poset of Dyck paths ordered by inclusion.
Number of antichains in the poset of Dyck paths ordered by inclusion.
Number of maximal antichains in the poset of Dyck paths ordered by inclusion.
Number of saturated chains in the poset of Dyck paths ordered by inclusion.
Array T(m,n) read by antidiagonals: number of domino tilings of the m X n grid (m>=0, n>=0).
Table of the elementary symmetric functions a_k(1,3,4,...,n+1).
Number of nonisomorphic graded posets with 0 and non-uniform Hasse graph of rank n, with exactly 2 elements of each rank above 0.
Number of nonisomorphic graded posets with 0 and non-uniform Hasse graph of rank n, with no 3-element antichain.
Irregular triangle read by rows: T(n, k) is the q-multinomial coefficient defined by the k-th partition of n in Abramowitz-Stegun order, evaluated at q = 2.
Irregular triangle read by rows: T(n, k) is the q-multinomial coefficient defined by the k-th partition of n in Abramowitz-Stegun order, evaluated at q = 3.
Irregular triangle read by rows: T(n, k) is the q-multinomial coefficient defined by the k-th partition of n in Abramowitz-Stegun order, evaluated at q = 4.
Irregular triangle read by rows: T(n, k) is the q-multinomial coefficient defined by the k-th partition of n in Abramowitz-Stegun order, evaluated at q = 5.
Irregular triangle read by rows: T(n, k) is the q-multinomial coefficient defined by the k-th partition of n in Abramowitz-Stegun order, evaluated at q = 7.
Irregular triangle read by rows: T(n, k) is the q-multinomial coefficient defined by the k-th partition of n in Abramowitz-Stegun order, evaluated at q = 8.
Irregular triangle read by rows: T(n, k) is the q-multinomial coefficient defined by the k-th partition of n in Abramowitz-Stegun order, evaluated at q = 9.
Irregular triangle read by rows: T(n, k) is the q-multinomial coefficient defined by the k-th partition of n in Abramowitz-Stegun order, evaluated at q = 11.
