Handbook of Enumerative Combinatorics

ISBN: 9781482220858 出版年：2015 页码：1,073 CRC Press

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 Branden 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-Schroder 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