Enumerative Combinatorics: Volume 2

by Richard P. Stanley , Appendix by Sergey Fomin

• ISBN13: 9780521789875
• ISBN10: 0521789877
• Format: Paperback
• Copyright: 2001-06-04
• Publisher: Cambridge University Press

Summary

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.

Table of Contents

Foreword	v
Preface	vii
Notation	xi
Trees and the Composition of Generating Functions	1	(158)
The Exponential Formula	1	(9)
Applications of the Exponential Formula	10	(12)
Enumeration of Trees	22	(14)
The Lagrange Inversion Formula	36	(8)
Exponential Structures	44	(10)
Oriented Trees and the Matrix-Tree Theorem	54	(105)
Notes	65	(4)
References	69	(3)
Exercises	72	(31)
Solutions to Exercises	103	(56)
Algebraic, D-Finite, and Noncommutative Generating Functions	159	(127)
Algebraic Generating Functions	159	(9)
Examples of Algebraic Series	168	(11)
Diagonals	179	(8)
D-Finite Generating Functions	187	(8)
Noncommutative Generating Functions	195	(7)
Algebraic Formal Series	202	(7)
Noncommutative Diagonals	209	(77)
Notes	211	(3)
References	214	(3)
Exercises	217	(32)
Solutions to Exercises	249	(37)
Symmetric Functions	286	(127)
Symmetric Functions in General	286	(1)
Partitions and Their Orderings	287	(2)
Monomial Symmetric Functions	289	(1)
Elementary Symmetric Functions	290	(4)
Complete Homogeneous Symmetric Functions	294	(2)
An Involution	296	(1)
Power Sum Symmetric Functions	297	(4)
Specializations	301	(5)
A Scalar Product	306	(2)
The Combinatorial Definition of Schur Functions	308	(8)
The RSK Algorithm	316	(6)
Some Consequences of the RSK Algorithm	322	(2)
Symmetry of the RSK Algorithm	324	(7)
The Dual RSK Algorithm	331	(3)
The Classical Definition of Schur Functions	334	(8)
The Jacobi-Trudi Identity	342	(3)
The Murnaghan-Nakayama Rule	345	(4)
The Characters of the Symmetric Group	349	(7)
Quasisymmetric Functions	356	(9)
Plane Partitions and the RSK Algorithm	365	(6)
Plane Partitions with Bounded Part Size	371	(7)
Reverse Plane Partitions and the Hillman-Grassl Correspondence	378	(4)
Applications to Permutation Enumeration	382	(8)
Enumeration under Group Action	390	(23)
Notes	396	(9)
References	405	(8)
A1 Knuth Equivalence, Jeu de Taquin, and the Littlewood-Richardson Rule	413	(27)
A1.1 Knuth Equivalence and Greene's Theorem	413	(6)
A1.2 Jeu de Taquin	419	(10)
A1.3 The Littlewood-Richardson Rule	429	(11)
Notes	437	(1)
References	438	(2)
A2 The Characters of GL(n, C)	440	(121)
Exercises	450	(40)
Solutions to Exercises	490	(71)
Index	561	(22)
Additional Errata and Addenda	583