1st Edition

Handbook of Enumerative Combinatorics

Edited By Miklos Bona Copyright 2015
    1086 Pages 225 B/W Illustrations
    by Chapman & Hall

    Presenting the state of the art, the Handbook of Enumerative Combinatorics brings together the work of today’s most prominent researchers. The contributors survey the methods of combinatorial enumeration along with the most frequent applications of these methods.

    This important new work is edited by Miklós Bóna of the University of Florida where he is a member of the Academy of Distinguished Teaching Scholars. He received his Ph.D. in mathematics at Massachusetts Institute of Technology in 1997. Miklós is the author of four books and more than 65 research articles, including the award-winning Combinatorics of Permutations. Miklós Bóna is an editor-in-chief for the Electronic Journal of Combinatorics and Series Editor of the Discrete Mathematics and Its Applications Series for CRC Press/Chapman and Hall.

    The first two chapters provide a comprehensive overview of the most frequently used methods in combinatorial enumeration, including algebraic, geometric, and analytic methods. These chapters survey generating functions, methods from linear algebra, partially ordered sets, polytopes, hyperplane arrangements, and matroids. Subsequent chapters illustrate applications of these methods for counting a wide array of objects.

    The contributors for this book represent an international spectrum of researchers with strong histories of results. The chapters are organized so readers advance from the more general ones, namely enumeration methods, towards the more specialized ones.

    Topics include coverage of asymptotic normality in enumeration, planar maps, graph enumeration, Young tableaux, unimodality, log-concavity, real zeros, asymptotic normality, trees, generalized Catalan paths, computerized enumeration schemes, enumeration of various graph classes, words, tilings, pattern avoidance, computer algebra, and parking functions.

    This book will be beneficial to a wide audience. It will appeal to experts on the topic interested in learning more about the finer points, readers interested in a systematic and organized treatment of the topic, and novices who are new to the field.

    METHODS

    Algebraic and Geometric Methods in Enumerative Combinatorics
    Introduction
    What is a Good Answer?
    Generating Functions
    Linear Algebra Methods
    Posets
    Polytopes
    Hyperplane Arrangements
    Matroids
    Acknowledgments

    Analytic Methods; Helmut Prodinger
    Introduction
    Combinatorial Constructions and Associated Ordinary Generating Functions
    Combinatorial Constructions and Associated Exponential Generating Functions
    Partitions and Q-Series
    Some Applications of the Adding a Slice Technique
    Lagrange Inversion Formula
    Lattice Path Enumeration: The Continued Fraction Theorem
    Lattice Path Enumeration: The Kernel Method
    Gamma and Zeta Function
    Harmonic Numbers and Their Generating Functions
    Approximation of Binomial Coefficients
    Mellin Transform and Asymptotics of Harmonic Sums
    The Mellin-Perron Formula
    Mellin-Perron Formula: Divide-and-Conquer Recursions
    Rice’s Method
    Approximate Counting
    Singularity Analysis of Generating Functions
    Longest Runs in Words
    Inversions in Permutations and Pumping Moments
    Tree Function
    The Saddle Point Method
    Hwang’s Quasi-Power Theorem

    TOPICS

    Asymptotic Normality in Enumeration; E. Rodney Canfield
    The Normal Distribution
    Method 1: Direct Approach
    Method 2: Negative Roots
    Method 3: Moments
    Method 4: Singularity Analysis
    Local Limit Theorems
    Multivariate Asymptotic Normality
    Normality in Service to Approximate Enumeration

    Trees
    ; Michael Drmota
    Introduction
    Basic Notions
    Generating Functions
    Unlabeled Trees
    Labeled Trees
    Selected Topics on Trees

    Planar maps; Gilles Schaeffer
    What is a Map?
    Counting Tree-Rooted Maps
    Counting Planar Maps
    Beyond Planar Maps, an Even Shorter Account

    Graph Enumeration; Marc Noy
    Introduction
    Graph Decompositions
    Connected Graphs with Given Excess
    Regular Graphs
    Monotone and Hereditary Classes
    Planar Graphs
    Graphs on Surfaces and Graph Minors
    Digraphs
    Unlabelled Graphs

    Unimodality, Log-Concavity, Real–Rootedness and Beyond; Petter Brándén
    Introduction
    Probabilistic Consequences of Real–Rootedness
    Unimodality and G-Nonnegativity
    Log–Concavity and Matroids
    Infinite Log-Concavity
    The Neggers–Stanley Conjecture
    Preserving Real–Rootedness
    Common Interleavers
    Multivariate Techniques
    Historical Notes

    Words;
    Dominique Perrin and Antonio Restivo
    Introduction
    Preliminaries
    Conjugacy
    Lyndon words
    Eulerian Graphs and De Bruijn Cycles
    Unavoidable Sets
    The Burrows-Wheeler Transform
    The Gessel-Reutenauer Bijection
    Suffix Arrays

    Tilings
    ; James Propp
    Introduction and Overview
    The Transfer Matrix Method
    Other Determinant Methods
    Representation-Theoretic Methods
    Other Combinatorial Methods
    Related Topics, and an Attempt at History
    Some Emergent Themes
    Software
    Frontiers

    Lattice Path Enumeration
    ; Christian Krattenthaler
    Introduction
    Lattice Paths Without Restrictions
    Linear Boundaries of Slope 1
    Simple Paths with Linear Boundaries of Rational Slope, I
    Simple Paths with Linear Boundaries with Rational Slope, II
    Simple Paths with a Piecewise Linear Boundary
    Simple Paths with General Boundaries
    Elementary Results on Motzkin and Schroder Paths
    A continued Fraction for the Weighted Counting of Motzkin Paths
    Lattice Paths and Orthogonal Polynomials
    Motzkin Paths in a Strip
    Further Results for Lattice Paths in the Plane
    Non-Intersecting Lattice Paths
    Lattice Paths and Their Turns
    Multidimensional Lattice Paths
    Multidimensional Lattice Paths Bounded by a Hyperplane
    Multidimensional Paths With a General Boundary
    The Reflection Principle in Full Generality
    Q-Counting Of Lattice Paths and Rogers–Ramanujan Identities
    Self-Avoiding Walks

    Catalan Paths and q; t-enumeration
    ; James Haglund
    Introduction to q-Analogues and Catalan Numbers
    The q; t-Catalan Numbers
    Parking Functions and the Hilbert Series
    The q; t-Schrӧder Polynomial
    Rational Catalan Combinatorics

    Permutation Classes; Vincent Vatter
    Introduction
    Growth Rates of Principal Classes
    Notions of Structure
    The Set of All Growth Rates

    Parking Functions
    ; Catherine H. Yan
    Introduction
    Parking Functions and Labeled Trees
    Many Faces of Parking Functions
    Generalized Parking Functions
    Parking Functions Associated with Graphs
    Final Remarks

    Standard Young Tableaux; Ron Adin and Yuval Roichman
    Introduction
    Preliminaries
    Formulas for Thin Shapes
    Jeu de taquin and the RS Correspondence
    Formulas for Classical Shapes
    More Proofs of the Hook Length Formula
    Formulas for Skew Strips
    Truncated and Other Non-Classical Shapes
    Rim Hook and Domino Tableaux
    q-Enumeration
    Counting Reduced Words
    Appendix 1: Representation Theoretic Aspects
    Appendix 2: Asymptotics and Probabilistic Aspects

    Computer Algebra; Manuel Kauers
    Introduction
    Computer Algebra Essentials
    Counting Algorithms
    Symbolic Summation
    The Guess-and-Prove Paradigm
    Index

    Biography

    Miklós Bóna received his Ph.D. in mathematics at Massachusetts Institute of Technology in 1997. Since 1999, he has taught at the University of Florida, where in 2010 he was inducted in the Academy of Distinguished Teaching Scholars. He is the author of four books and more than 65 research articles, mostly focusing on enumerative and analytic combinatorics. His book Combinatorics of Permutations won the Outstanding Title Award from Choice, the journal of the American Library Association. He has mentored numerous graduate and undergraduate students. Miklós Bóna is an editor-in-chief for the Electronic Journal of Combinatorics, and for two book series at CRC Press.

    "Mathematical handbooks are among the most essential library resources, providing compilations of formulas, tables, graphs, etc. Traditional handbooks speak equally to experts and casual users of mathematics. Other handbooks, such as the current work, are really encyclopedic compendiums of survey articles primarily addressing readers who make mathematics their main business. They supplement systematic monographs that develop subjects methodically but require extreme reader commitment and journal literature that provides quick access to specific results for those with prerequisite knowledge. Researchers will benefit from rapid authoritative citations to newer or lesser-known results. Students, undergraduate and graduate, will find accessible, systematic snapshots of whole subjects, helping them discover what they most wish to learn and, equally, what they will then need to learn on the way. Enumerative combinatorics means counting problems, so that subject begins classically with permutations and combinations but is active now with connections to probability, graph theory, statistical mechanics, geometry, representation theory, analysis, and computer science. Chapters here divide between general counting methods, both exact and approximate, and special classes of objects for counting via any suitable means. The volume, part of the 'Discrete Mathematics and Its Applications' series, is well edited by Bóna (Univ. of Florida), who successfully pools the expertise of leaders in the field. Summing up: Recommended. Upper-division undergraduates through professionals/practitioners."
    —D. V. Feldman, University of New Hampshire, Durham, USA, for CHOICE, March 2016

    "I cannot think of any topic that I would like to have seen presented here that the book omits. The chapters discuss not only methods in the study of enumerative combinatorics, but also objects that lend themselves to study along these lines. … accessible to a wide audience … this will clearly be a book that anybody with a serious interest in combinatorics will want to have on his or her bookshelf, and of course it belongs in any self-respecting university library. Having seen firsthand what it takes to edit a handbook like this, I know that Miklós Bóna must have invested a great deal of time and effort in the creation of this volume, as did the authors of the individual chapters. Their efforts have not been in vain; this is a valuable book."
    MAA Reviews, July 2015