You are previewing Enumerative Combinatorics.
O'Reilly logo
Enumerative Combinatorics

Book Description

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

  1. Cover
  2. Title
  3. Copyright
  4. Foreword
  5. Preface
  6. Contents
  7. Notation
  8. 5 Trees and the Composition of Generating Functions
    1. 5.1 The Exponential Formula
    2. 5.2 Applications of the Exponential Formula
    3. 5.3 Enumeration of Trees
    4. 5.4 The Lagrange Inversion Formula
    5. 5.5 Exponential Structures
    6. 5.6 Oriented Trees and the Matrix–Tree Theorem
    7. Notes
    8. References
    9. Exercises
    10. Solutions to Exercises
  9. 6 Algebraic, D-Finite, and Noncommutative Generating Functions
    1. 6.1 Algebraic Generating Functions
    2. 6.2 Examples of Algebraic Series
    3. 6.3 Diagonals
    4. 6.4 D-Finite Generating Functions
    5. 6.5 Noncommutative Generating Functions
    6. 6.6 Algebraic Formal Series
    7. 6.7 Noncommutative Diagonals
    8. Notes
    9. References
    10. Exercises
    11. Solutions to Exercises
  10. 7 Symmetric Functions
    1. 7.1 Symmetric Functions in General
    2. 7.2 Partitions and Their Orderings
    3. 7.3 Monomial Symmetric Functions
    4. 7.4 Elementary Symmetric Functions
    5. 7.5 Complete Homogeneous Symmetric Functions
    6. 7.6 An Involution
    7. 7.7 Power Sum Symmetric Functions
    8. 7.8 Specializations
    9. 7.9 A Scalar Product
    10. 7.10 The Combinatorial Definition of Schur Functions
    11. 7.11 The RSK Algorithm
    12. 7.12 Some Consequences of the RSK Algorithm
    13. 7.13 Symmetry of the RSK Algorithm
    14. 7.14 The Dual RSK Algorithm
    15. 7.15 The Classical Definition of Schur Functions
    16. 7.16 The Jacobi-Trudi Identity
    17. 7.17 The Murnaghan-Nakayama Rule
    18. 7.18 The Characters of the Symmetric Group
    19. 7.19 Quasisymmetric Functions
    20. 7.20 Plane Partitions and the RSK Algorithm
    21. 7.21 Plane Partitions with Bounded Part Size
    22. 7.22 Reverse Plane Partitions and the Hillman–Grassl Correspondence
    23. 7.23 Applications to Permutation Enumeration
    24. 7.24 Enumeration under Group Action
    25. Notes
    26. References
  11. A 1 Knuth Equivalence, Jeu de Taquin, and the Littlewood-Richardson Rule
    1. A1.1 Knuth Equivalence and Greene’s Theorem
    2. A 1.2 Jeu de Taquin
    3. A1.3 The Littlewood–Richardson Rule
    4. Notes
    5. References
  12. A2 The Characters of GL(n, ℂ)
    1. Exercises
    2. Solutions to Exercises
  13. Index
  14. Additional Errata and Addenda