Generatingfunctionology : Third Edition

Generating functions, one of the most important tools in enumerative combinatorics, are a bridge between discrete mathematics and continuous analysis. Generating functions have numerous applications in mathematics, especially in - Combinatorics - Probability Theory - Statistics - Theory of Markov Chains - Number Theory One of the most important and relevant recent applications of combinatorics lies in the development of Internet search engines whose incredible capabilities dazzle even the mathematically trained user. This new edition includes several new areas of application, including the cycle index of the symmetric group, permutations, and square roots, counting polyminoes, and exact covering sequences. An appendix on using Maple and Mathematica to generate applications is also included. Includes exercises and solutions at the end of each chapter. Front Cover Title Copyright Contents Preface 1. Introductory Ideas and Examples 1.1 An Easy Two Term Recurrence 1.2 A Slightly Harder Two Term Recurrence 1.3 A Three Term Recurrence 1.4 A Three Term Boundary Value Problem 1.5 Two Independent Variables 1.6 Another 2-Variable Case . 1.7 Exercises 2. Series 2.1 Formal Power Series 2.2 The Calculus of Formal Ordinary Power Series Generating Functions 2.3 The Calculus of Formal Exponential Generating Functions 2.4 Power Series, Analytic Theory 2.5 Some Useful Power Series 2.6 Dirichlet Series, Formal theory 2.7 Exercises 3. Cards, Decks, and Hands: The Exponential Formula 3.1 Introduction 3.2 Definitions and a Question 3.3 Examples of Exponential Families 3.4 The Main Counting Theorems 3.5 Permutations and Their Cycles 3.6 Set Partitions 3.7 A Subclass of Permutations 3.8 Involutions, etc 3.9 2-Regular Graphs 3.10 Counting Connected Graphs 3.11 Counting Labeled Bipartite Graphs 3.12 Counting Labeled Trees 3.13 Exponential Families and Polynomials of 'Binomial Type.' 3.14 Unlabeled Cards and Hands 3.15 The Money Changing Problem 3.16 Partitions of Integers 3.17 Rooted Trees and Forests 3.18 Historical Notes 3.19 Exercises 4. Applications of Generating Functions 4.1 Generating Functions Find Averages, etc. 4.2 A Generatingfunctionological View of the Sieve Method 4.3 The 'Snake Oil' Method for Easier Combinatorial Identities 4.4 WZ Pairs Prove Harder Identities 4.5 Generating Functions and Unimodality, Convexity, etc. 4.6 Generating Functions Prove Congruences 4.7 The Cycle Index of the Symmetric Group 4.8 How Many Permutations Have Square Roots? 4.9 Counting Polyominoes 4.10 Exact Covering Sequences 4.11 Waiting for a String 4.12 Blocks of 1's 4.13 Exercises 5. Analytic and Asymptotic Methods 5.1 The Lagrange Inversion Formula 5.2 Analyticity and Asymptotics (I): Poles 5.3 Analyticity and Asymptotics (II): Algebraic Singularities 5.4 Analyticity and Asymptotics (III): Hayman's Method 5.5 Exercises A. Using Maple and Mathematica A.1 Series Manipulation A.2 The RSolve.m Routine A.3 Asymptotics in Maple Solutions References Back Cover A generating function is a clothesline on which we hang up a sequence of numbers for display.