John Riordan - Introduction to Combinatorial Analysis

An Introduction
to Combinatorial Analysis John Riordan DOVER PUBLICATIONS, INC.
Mineola, New York Bibliographical Note This Dover edition, first published in 2002, is an unabridged republication of the work first published by John Wiley & Sons, Inc., New York, in 1958. The errata list was added in a later printing. Library of Congress Cataloging-in-Publication Data Riordan, John, 1903 Introduction to combinatorial analysis / John Riordan.Dover ed. p. cm. Originally published: New York : John Wiley, 1958.

Includes bibliographical references and index. eISBN 13: 978-0-486-15440-4 1. Combinatorial analysis. I. Title: Combinatorial analysis. Title. Title.

QA164 .R53 2002
511.6dc21 2002073535 Manufactured in the United States of America
Dover Publications, Inc., 31 East 2nd Street, Mineola, N.Y. 11501 To E. T. Bell Errata

PAGE	LINE	CORRECTION
14	exp(m(t)) for m(t)
7b	(45)for(44)
13	t2/2! for t2
8b	Remove half-parenthesis before Sk+1
5b	p. 241 for p. 205
16	for
7	dnr + 1(t, r) for dnr + 1(t)
2	r(x) for r2(x)
20	[(1 t)(1 t2)(1 t2)] for [(1 t)(1 t2) (1 tk)]k
15	Ist. Veneto tor Inst. Veneto
7b	(52)for(51)
14	(52)for(51)
18	(52)for(51)
8	(No. 4, 1950) for (1949)
20	Add (r 1 )n (r 1)n to gn = [(r 1) 2]n

Notation: line 7b (e.g.) is the seventh line from below. Preface COMBINATORIAL ANALYSIS, THOUGH A WELL-RECOGNIZED PART of mathematics, seems to have a poorly defined range and position. Leibniz, in his ars combinatoria, was the originator of the subject, apparently in the sense of Netto (Lehrbuch der Combinatorik, Leipzig, 1901) as the consideration of the placing, ordering, or choice of a number of things together. A. A.

Whitworth, fifth edition, London, 1901), of one of the few books in English on the subject. This superb title also suggests the close relation of the subject to the theory of probability. P. A. MacMahon, in the most ambitious treatise on the subject (Combinatory Analysis, London, vol. I, 1915, vol.

II, 1916), says merely that it occupies the ground between algebra and the higher arithmetic, meaning by the latter, as he later explains, what is now called the Theory of Numbers. A current American dictionary (Funk and Wagnalls New Standard, 1943) defines combinatorica convenient single word which appears now and then in the present textas a department of mathematics treating of the formation, enumeration, and properties of partitions, variations, combinations, and permutations of a finite number of elements under various conditions. The term combinatorial analysis itself, seems best explained by the following quotation from Augustus DeMorgan (Differential and Integral Calculus, London, 1842, p. 335): the combinatorial analysis mainly consists in the analysis of complicated developments by means of a priori consideration and collection of the different combinations of terms which can enter the coefficients. No one of these statements is satisfactory in providing a safe and sure guide to what is and what is not combinatorial. The authors of the three textbooks could be properly vague because their texts showed what they meant.

The dictionary, in describing the contents of such texts, allows no room for new applications of combinatorial technique (such as appear in the last half of of the present text in the enumeration of trees, networks, and linear graphs). DeMorgans statement is admirable but half-hearted; in present language, it recognizes that coefficients of generating functions may be determined by solution of combinatorial problems, but ignores the reverse possibility that combinatorial problems may be solved by determining coefficients of generating functions. Since the subject seems to have new growing ends, and definition is apt to be restrictive, this lack of conceptual precision may be all for the best. So far as the present book is concerned, anything enumerative is combinatorial; that is, the main emphasis throughout is on finding the number of ways there are of doing some well-defined operation. This includes all the traditional topics mentioned in the dictionary definition quoted above; therefore this book is suited to the purpose of presenting an introduction to the subject. It is sufficiently vague to include new material, like that mentioned above, and thus it is suited to the purpose of presenting this introduction in an up-to-date form.

The modern developments of the subject are closely associated with the use of generating functions. As appears even in the first chapter, these must be taken in a form more general than the power series given them by P. S. Laplace, their inventor. Moreover, for their combinatorial uses, they are to be regarded, following E. T.

Bell, as tools in the theory of an algebra of sequences, so that despite all appearances they belong to algebra and not to analysis. They serve to compress a great deal of development and allow the presentation of a mass of results in a uniform manner, giving the book more scope than would have been possible otherwise. By their means, that central combinatorial tool, the method of inclusion and exclusion, may be shown to be related to the use of factorial moments (which should be attractive to the statistician). Finally, the presentation in this form fits perfectly with the presentation of probability given by William Feller in this series. As to the contents, the following remarks may be useful. have been mentioned above and are devoted to elaboration of work at the start of which I was fortunate to have the collaboration of Irving Kaplansky; the continuance of this work owes much to correspondence with both Touchard and Koichi Yamamoto; the development not otherwise accredited is my own.

Each chapter has an extensive problem section, which is intended to carry on the development of the text, and so extend the scope of the book in a way which would have been impossible otherwise. So far as possible, the problems are put in a form to aid rather than baffle the reader; nevertheless, they assume a certain amount of mathematical maturity, that favorite phrase of textbook preface writers, by which I hope they mean a sufficient interest in the subject to do the work necessary to master it. This aid to the reader is also offered in the sequence in which they are set down, which is intended to carry him forward in a natural way. As to notation, I have limited myself for the most part to English letters, which has entailed using many of these in several senses. So far as possible, these multiple uses have been separated by a decent interval, and warnings have been inserted where confusion seemed likely. The reader now is warned further by this statement.

Equations, theorems, sections, examples, and problems are numbered consecutively in each chapter and are referred to by these numbers in their own chapter; in other chapters, their chapter number is prefixed. Thus . Numbers in bold type following proper names indicate items in the list of references of that chapter. The range of tables is often indicated in the abbreviated fashion currently common: n = 0(1)10 means that n has the values 0, 1, 2, , 10. I have made a point of carrying the development to where the actual numbers in question can be obtained as simply as possible; some otherwise barren wastes of algebra are justified by this consideration. In some cases, these numbers are so engaging as to invite consideration of their arithmetical structure (the congruences they satisfy), which I have included, quoting, but not proving, the required results from number theory.

Next page