Wilf Generating Functionology

2. Auflage 2013
ISBN: 978-0-08-057151-5
Verlag: Elsevier Science & Techn.
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 228 Seiten, Web PDF

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

Autoren/Hrsg.

Wilf, Herbert S.

Inhaltsverzeichnis

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