Generating Functionology (eBook)

Herbert S. Wilf (Autor)

eBook Download: PDF

2013 | 2. Auflage
228 Seiten
Elsevier Science (Verlag)
978-0-08-057151-5 (ISBN)

Infos

This is the Second Edition of the highly successful introduction to the use of generating functions and series in combinatorial mathematics. This new edition includes several new areas of application, including the cycle index of the symmetric group, permutations and square roots, counting polyominoes, and exact covering sequences. An appendix on using the computer algebra programs MAPLE(r) and Mathematica(r) to generate functions is also included. The book provides a clear, unified introduction to the basic enumerative applications of generating functions, and includes exercises and solutions, many new, at the end of each chapter. - Provides new applications on the cycle index of the symmetric group, permutations and square roots, counting polyominoes, and exact covering sequences - Features an Appendix on using MAPLE(r) and Mathematica (r) to generate functions - Includes many new exercises with complete solutions at the end of each chapter

Inhalt

Front Cover 1
Generatingfunctionology 4
Copyright Page 5
Table of Contents 6
Preface 8
Preface to the Second Edition 10
Chapter 1: Introductory Ideas and Examples 12
1.1 An easy two term recurrence 14
1.2 A slightly harder two term recurrence 16
1.3 A three term recurrence 19
1.4 A three term boundary value problem 21
1.5 Two independent variables 22
1.6 Another 2-variable case 27
Exercises 35
Chapter 2: Series 41
2.1 Formal power series 41
2.2 The calculus of formal ordinary power series generating functions 44
2.3 The calculus of formal exponential generating functions 50
2.4 Power series, analytic theory 57
2.5 Some useful power series 63
2.6 Dirichlet series, formal theory 67
Exercises 76
Chapter 3: Cards, Decks, and Hands: The Exponential Formula 84
3.1 Introduction 84
3.2 Definitions and a question 85
3.3 Examples of exponential families 87
3.4 The main counting theorems 89
3.5 Permutations and their cycles 92
3.6 Set partitions 94
3.7 A subclass of permutations 95
3.8 Involutions, etc 95
3.9 2-regular graphs 96
3.10 Counting connected graphs 97
3.11 Counting labeled bipartite graphs 98
3.12 Counting labeled trees 100
3.13 Exponential families and polynomials of 'binomial type.' 102
3.14 Unlabeled cards and hands 103
3.15 The money changing problem 107
3.16 Partitions of integers 111
3.17 Rooted trees and forests 113
3.18 Historical notes 114
Exercise 115
Chapter 4: Applications of generating functions 119
4.1 Generating functions find averages, etc 119
4.2 A generatingfunctionological view of the sieve method 121
4.3 The 'Snake Oil' method for easier combinatorial identities 129
4.4 WZ pairs prove harder identities 141
4.5 Generating functions and unimodality, convexity, etc 147
4.6 Generating functions prove congruences 151
4.7 The cycle index of the symmetric group 152
4.8 How many permutations have square roots 157
4.9 Counting polyominoes 161
4.10 Exact covering sequences 165
Exercises 168
Chapter 5: Analytic and asymptotic methods 178
5.1 The Lagrange Inversion Formula 178
5.2 Analyticity and asymptotics (I): Poles 182
5.3 Analyticity and asymptotics (II): Algebraic singularities 188
5.4 Analyticity and asymptotics (III): Hayman's method 192
Exercises 199
Appendix: Using Mapl™ and Mathematical™ 203
Solutions 208
References 235
Index 238

Produkt-Details

• Erscheint lt. Verlag: 22.10.2013
• Sprache: englisch
• Themenwelt: Informatik ► Software Entwicklung ► User Interfaces (HCI)
• Themenwelt: Mathematik / Informatik ► Mathematik
• Themenwelt: Technik
• ISBN-10: 0-08-057151-4 / 0080571514
• ISBN-13: 978-0-08-057151-5 / 9780080571515