An introduction to combinatorial analysis / John Riordan

Index

This is the only modern book on combinatorial analysis. It will be extremely useful to anyone who wishes to make a systematic study of the subject, as well as to the many mathematicians and mathematical practitioners who are sometimes faced with particular problems involving a count of the number of ways in which some well defined operation can be carried out. Techniques developed in this book are of increasing importance in the study of modern statistics, computing devices, communications engineering and in the recent applications of graph theory to chemistry and problems in the social sciences. The book contains an excellent review of classical material, but most of it is devoted to a unified exposition, insofar as possible, of recent developments. A number of these are due to the author. The usefulness of the book is greatly enhanced by the extensive references to the modern literature and by the many results given in problem form at the end of each chapter. Powerful methods are developed in a subject which has seemed to many to be merely a collection of special tricks. These methods are given vitality by their application to many difficult problems of enumeration. An outline of the contents follows. Chapter 1 covers the elementary theory of permutations and combinations and introduces the unifying concept of generating function. In chapter 2 the relation between ordinary and exponential generating functions is developed. The Blissard notation is introduced and linear recurrences are treated. Moment generating functions and Stirling numbers are introduced. Derivatives of composite functions and the related Bell polynomials are considered. Chapter 3 develops the method of inclusion and exclusion. Chapter 4 deals mainly with the work of Touchard on enumeration of permutations with given cycle character. Chapter 5 treats distribution and occupancy problems involving both like and unlike objects in both like and unlike cells. The first part of chapter 6 treats the elementary theory of partitions, including Franklin's proof of Euler's recurrence for the partition function. Ordered partitions are also treated. The second and more novel part of this chapter develops the powerful enumeration theory of Pólya and applies it to a variety of graph enumeration results. The problems in this and in the remaining chapters are particularly rich in content. Chapters 7 and 8 deal with permutations with restricted positions. The main problems here are formulated in terms of configurations of non-attacking rooks on "chessboards'' of various shapes. The interesting methods are due mainly to Riordan and Kaplansky. In the two-volume treatise by MacMahon [Combinatory analysis, University Press, Cambridge, 1915–16] many enumeration problems were claimed to be solved when, in fact, they were merely reformulated. In this book such an approach is avoided. Explicit formulae are the order of the day and in many cases the formulae are accompanied by short tables. Nevertheless, the author is usually satisfied with an explicit formula, even though it may be comparatively unmanageable for large values of the arguments. Very little is said about asymptotic developments for such cases. There are many problems usually considered combinatorial in nature in which the question is not primarily "in how many ways can this be done'' but rather "can this be done in at least one way?'' These include important problems of finite geometries, difference sets and related combinatorial designs. Such problems are not treated here. These omissions are indications of the size of the subject rather than of the shortcomings of the book. In fact, the author has admirably succeeded in marshalling many interesting facts that were not nearly so accessible before. He has infused pattern and order into his subject and will thereby, we hope, attract more mathematicians to this fascinating field. (MathSciNet).