×

Combinatorial methods in discrete mathematics. Transl. from the Russian by V. Kolchin. (English) Zbl 0845.05003

Encyclopedia of Mathematics and Its Applications. 55. Cambridge: Cambridge Univ. Press. xiii, 306 p. (1995).
This book is primarily an exposition of the fundamentals of enumeration theory. It presents these fundamentals as a set of tools “for the investigation of various models of functioning of technical devices and discretely operating systems”. The book is written for a (mathematically) mature audience and is a suitable text for a graduate level course in enumeration.
Chapter 1 is devoted to an introduction to a wide variety of combinatorial objects, e.g. Latin squares, projective planes, block designs. Many of the counting problems that illustrate the technique and theories as they are developed come from these areas and from transversal theory, the subject of Chapter 2. The number of transversals is interpreted as a permanent. Various methods for evaluating permanents are developed here. Inclusion-exclusion and the general theory of inversion on a partially ordered set are also included in Chapter 2.
Generating functions are the focus of Chapter 3. They are introduced in the context of the ring of formal power series. Special attention is paid to asymptotic results. “If a generating function is an analytic function, we can find an asymptotic representation of the coefficients using the saddle point method, well known in complex analysis for the estimation of contour integrals.”
The basics of graph theory are introduced in Chapter 4 and the early sections of the chapter discuss many of the usual counting problems associated with graphs, e.g. the number of labeled graphs with \(n\) vertices and \(m\) edges and the number of trees on \(n\) vertices. The remainder of the chapter is devoted to problems which can be converted to counting problems on graphs, e.g. the number of representations of a permutation as a product of the minimum number of transpositions. Probabilistic methods for enumeration are introduced here and applied to several problems.
In Chapter 5, the author introduces his “general combinatorial scheme” which is essentially the equivalence classes of functions from a set \(X\) into a set \(A\) under the combined actions of two groups acting on \(X\) and \(A\), respectively. A wide variety of problems, some previously discussed, are placed in this context. As with the earlier chapters, special attention is given to asymptotic behavior. The derivation of the Hardy-Ramanujan asymptotic formula for the number of partitions of \(m\) as \(m\) goes to infinity is one of the highlights of this chapter. Chapter 6 builds on Chapter 5 giving an exposition of Polya’s counting theorem and its extension by de Bruijn.

MSC:

05A15 Exact enumeration problems, generating functions
05-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to combinatorics
05B20 Combinatorial aspects of matrices (incidence, Hadamard, etc.)
05B05 Combinatorial aspects of block designs
05C05 Trees
05B15 Orthogonal arrays, Latin squares, Room squares
05C38 Paths and cycles

Citations:

Zbl 0629.05001
PDF BibTeX XML Cite