generatingfunctionology

generatingfunctionology Herbert S. Wilf Department of Mathematics University of Pennsylvania Philadelphia, Pennsylvania Copyright 1990 and 1994 by Academic Press, Inc. All rights re-served. This Internet Edition may be reproduced for any valid educational purpose of an institution of higher learning, in which case only the reason-able costs of reproduction may be charged. Reproduction for profit or for any commercial purposes is strictly prohibited. vi Preface This book is about generating functions and some of their uses in discrete mathematics. The subject is so vast that I have not attempted to give a comprehensive discussion. Instead I have tried only to communicate some of the main ideas. Generating functions are a bridge between discrete mathematics, on the one hand, and continuous analysis (particularly complex variable the-ory) on the other. It is possible to study them solely as tools for solving discrete problems. As such there is much that is powerful and magical in the way generating functions give unified methods for handling such prob-lems. The reader who wished to omit the analytical parts of the subject would skip chapter 5 and portions of the earlier material. To omit those parts of the subject, however, is like listening to a stereo broadcast of, say, Beethoven’s Ninth Symphony, using only the left audio channel. The full beauty of the subject of generating functions emerges only from tuning in on both channels: the discrete and the continuous. See how they make the solution of difference equations into child’s play. Then see how the theory of functions of a complex variable gives, virtually by inspection, the approximate size of the solution. The interplay between the two channels is vitally important for the appreciation of the music. In recent years there has been a vigorous trend in the direction of finding bijective proofs of combinatorial theorems. That is, if we want to prove that two sets have the same cardinality then we should be able to do it by exhibiting an explicit bijection between the sets. In many cases the fact that the two sets have the same cardinality was discovered in the first place by generating function arguments. Also, even though bijective arguments may be known, the generating function proofs may be shorter or more elegant. The bijective proofs give one a certain satisfying feeling that one ‘re-ally’ understands why the theorem is true. The generating function argu-ments often give satisfying feelings of naturalness, and ‘oh, I could have thought of that,’ as well as usually offering the best route to finding exact or approximate formulas for the numbers in question. This book was tested in a senior course in discrete mathematics at the University of Pennsylvania. My thanks go to the students in that course for helping me at least partially to debug the manuscript, and to a number of my colleagues who have made many helpful suggestions. Any reader who is kind enough to send me a correction will receive a then-current complete errata sheet and many thanks. Herbert S. Wilf Philadelphia, PA September 1, 1989 vii Preface to the Second Edition This edition contains several new areas of application, in chapter 4, many new problems and solutions, a number of improvements in the pre-sentation, and corrections. It also contains an Appendix that describes some of the features of computer algebra programs that are of particular importance in the study of generating functions. I am indebted to many people for helping to make this a better book. Bruce Sagan, in particular, made many helpful suggestions as a result of a test run in his classroom. Many readers took up my offer (which is now repeated) to supply a current errata sheet and my thanks in return for any errors discovered. Herbert S. Wilf Philadelphia, PA May 21, 1992 viii CONTENTS Chapter 1: Introductory Ideas and Examples 1.1 An easy two term recurrence . . . . . . . . . . . . . . . . . 3 1.2 A slightly harder two term recurrence . . . . . . . . . . . . . 5 1.3 A three term recurrence . . . . . . . . . . . . . . . . . . . 8 1.4 A three term boundary value problem . . . . . . . . . . . . 10 1.5 Two independent variables . . . . . . . . . . . . . . . . . 11 1.6 Another 2-variable case . . . . . . . . . . . . . . . . . . 16 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . 24 Chapter 2: Series 2.1 Formal power series . . . . . . . . . . . . . . . . . . . . 30 2.2 The calculus of formal ordinary power series generating functions 33 2.3 The calculus of formal exponential generating functions . . . . 39 2.4 Power series, analytic theory . . . . . . . . . . . . . . . . 46 2.5 Some useful power series . . . . . . . . . . . . . . . . . . 52 2.6 Dirichlet series, formal theory . . . . . . Exercises . . . . . . . . . . . . . . . . . . . . . . . . . 56 . . . . . . . . . 65 Chapter 3: Cards, Decks, and Hands: The Exponential Formula 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . 73 3.2 Definitions and a question . . . . . . . . . . . . . . . . . 74 3.3 Examples of exponential families . . . . . . . . . . . . . . 76 3.4 The main counting theorems . . . . . . . . . . . . . . . . 78 3.5 Permutations and their cycles . . . . . . . . . . . . . . . 81 3.6 Set partitions . . . . . . . . . . . . . . . . . . . . . . . 83 3.7 A subclass of permutations . . . . . . . . . . . . . . . . . 84 3.8 Involutions, etc. 3.9 2-regular graphs . . . . . . . . . . . . . . . . . . . . . 84 . . . . . . . . . . . . . . . . . . . . . 85 3.10 Counting connected graphs . . . . . . . . . . . . . . . . . 86 3.11 Counting labeled bipartite graphs . . . . . . . . . . . . . . 87 3.12 Counting labeled trees . . . . . . . . . . . . . . . . . . . 89 3.13 Exponential families and polynomials of ‘binomial type.’ . . . . 91 3.14 Unlabeled cards and hands . . . . . . . . . . . . . . . . . 92 3.15 The money changing problem 3.16 Partitions of integers . . . . . . . . . . . . . . . . . . . 96 . . . . . . . . . . . . . . . 100 3.17 Rooted trees and forests . . . . . . . . . . . . . . . . . . 102 3.18 Historical notes . . . . . . . . . . . . . . . . . . . . . . 103 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . 104 vii Chapter 4: Applications of generating functions 4.1 Generating functions find averages, etc. . . . . . . . . . . . 108 4.2 A generatingfunctionological view of the sieve method . . . . . 110 4.3 The ‘Snake Oil’ method for easier combinatorial identities . . . 118 4.4 WZ pairs prove harder identities . . . . . . . . . . . . . . 130 4.5 Generating functions and unimodality, convexity, etc. . . . . . 136 4.6 Generating functions prove congruences 4.7 The cycle index of the symmetric group . . . . . . . . . . . 140 . . . . . . . . . . . 141 4.8 How many permutations have square roots? . . . . . . . . . 146 4.9 Counting polyominoes . . . . . . . . . . . . . . . . . . . 150 4.10 Exact covering sequences . Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 . . . . . . . . . 157 Chapter 5: Analytic and asymptotic methods 5.1 The Lagrange Inversion Formula . . . . . . . . . . . . . . 167 5.2 Analyticity and asymptotics (I): Poles . . . . . . . . . . . . 171 5.3 Analyticity and asymptotics (II): Algebraic singularities . . . . 177 5.4 Analyticity and asymptotics (III): Hayman’s method . . . . . 181 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . 188 Appendix: Using MapleTM and MathematicaTM . . . . . . . . 192 Solutions . . . . . . . . . . . . . . . . . . . . . . . . 197 References . . . . . . . . . . . . . . . . . . . . . . . 224 viii ... - tailieumienphi.vn