This second volume of a two-volume basic introduction to enumerative combinatorics covers the composition of generating functions, trees, algebraic generating functions, D-finite generating functions, noncommutative generating functions, and symmetric functions. The chapter on symmetric functions provides the only available treatment of this subject suitable for an introductory graduate course on combinatorics, and includes the important Robinson-Schensted-Knuth algorithm. Also covered are connections between symmetric functions and representation theory. An appendix by Sergey Fomin covers some deeper aspects of symmetric function theory, including jeu de taquin and the Littlewood-Richardson rule. As in Volume 1, the exercises play a vital role in developing the material. There are over 250 exercises, all with solutions or references to solutions, many of which concern previously unpublished results. Graduate students and research mathematicians who wish to apply combinatorics to their work will find this an authoritative reference.
Author(s): Richard P. Stanley, Sergey Fomin
Series: Cambridge Studies in Advanced Mathematics 62
Edition: Paperback Edition
Publisher: Cambridge University Press
Year: 2001
Language: English
Pages: 598
Tags: Generating Functions, Symmetric Functions
Foreword......Page 6
Preface......Page 8
Contents......Page 10
Notation......Page 12
5.1 The Exponential Formula......Page 14
5.2 Applications of the Exponential Formula......Page 23
5.3 Enumeration of Trees......Page 35
5.4 The Lagrange Inversion Formula......Page 49
5.5 Exponential Structures......Page 57
5.6 Oriented Trees and the Matrix-Tree Theorem......Page 67
Notes......Page 78
References......Page 82
Exercises......Page 85
Solutions to Exercises......Page 116
6.1 Algebraic Generating Functions......Page 172
6.2 Examples of Algebraic Series......Page 181
6.3 Diagonals......Page 192
6.4 D-Finite Generating Functions......Page 200
6.5 Noncommutative Generating Functions......Page 208
6.6 Algebraic Formal Series......Page 215
6.7 Noncommutative Diagonals......Page 222
Notes......Page 224
References......Page 227
Exercises......Page 230
Solutions to Exercises......Page 262
7.1 Symmetric Functions in General......Page 299
7.2 Partitions and Their Orderings......Page 300
7.3 Monomial Symmetric Functions......Page 302
7.4 Elementary Symmetric Functions......Page 303
7.5 Complete Homogeneous Symmetric Functions......Page 307
7.6 An Involution......Page 309
7.7 Power Sum Symmetric Functions......Page 310
7.8 Specializations......Page 314
7.9 A Scalar Product......Page 319
7.10 The Combinatorial Definition of Schur Functions......Page 321
7.11 The RSK Algorithm......Page 329
7.12 Some Consequences of the RSK Algorithm......Page 335
7.13 Symmetry of the RSK Algorithm......Page 337
7.14 The Dual RSK Algorithm......Page 344
7.15 The Classical Definition of Schur Functions......Page 347
7.16 The Jacobi-Trudi Identity......Page 355
7.17 The Murnaghan-Nakayama Rule......Page 358
7.18 The Characters of the Symmetric Group......Page 362
7.19 Quasisymmetric Functions......Page 369
7.20 Plane Partitions and the RSK Algorithm......Page 378
7.21 Plane Partitions with Bounded Part Size......Page 384
7.22 Reverse Plane Partitions and the Hillman-Grass]. Correspondence......Page 391
7.23 Applications to Permutation Enumeration......Page 395
7.24 Enumeration under Group Action......Page 403
Notes......Page 409
References......Page 418
A1.1 Knuth Equivalence and Greene's Theorem......Page 426
A1.2 Jeu de Taquin......Page 432
A1.3 The Littlewood-Richardson Rule......Page 442
Notes......Page 450
References......Page 451
A 2 The Characters of GL(n, C)......Page 453
Exercises......Page 463
Solutions to Exercises......Page 503
Index......Page 574
Additional Errata and Addenda......Page 596
