Handbook of Enumerative Combinatorics

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.

METHODSAlgebraic and Geometric Methods in Enumerative CombinatoricsIntroductionWhat is a Good Answer?Generating FunctionsLinear Algebra MethodsPosetsPolytopesHyperplane ArrangementsMatroidsAcknowledgmentsAnalytic Methods; Helmut ProdingerIntroductionCombinatorial Constructions and Associated Ordinary Generating Functions Combinatorial Constructions and Associated Exponential Generating Functions Partitions and Q-SeriesSome Applications of the Adding a Slice TechniqueLagrange Inversion FormulaLattice Path Enumeration: The Continued Fraction TheoremLattice Path Enumeration: The Kernel MethodGamma and Zeta Function Harmonic Numbers and Their Generating FunctionsApproximation of Binomial CoefficientsMellin Transform and Asymptotics of Harmonic SumsThe Mellin-Perron FormulaMellin-Perron Formula: Divide-and-Conquer Recursions Rice’s MethodApproximate CountingSingularity Analysis of Generating FunctionsLongest Runs in WordsInversions in Permutations and Pumping MomentsTree FunctionThe Saddle Point MethodHwang’s Quasi-Power TheoremTOPICSAsymptotic Normality in Enumeration; E. Rodney CanfieldThe Normal DistributionMethod 1: Direct ApproachMethod 2: Negative RootsMethod 3: MomentsMethod 4: Singularity AnalysisLocal Limit TheoremsMultivariate Asymptotic NormalityNormality in Service to Approximate EnumerationTrees; Michael DrmotaIntroductionBasic NotionsGenerating FunctionsUnlabeled TreesLabeled TreesSelected Topics on TreesPlanar maps; Gilles SchaefferWhat is a Map?Counting Tree-Rooted MapsCounting Planar MapsBeyond Planar Maps, an Even Shorter AccountGraph Enumeration; Marc NoyIntroductionGraph DecompositionsConnected Graphs with Given ExcessRegular GraphsMonotone and Hereditary ClassesPlanar GraphsGraphs on Surfaces and Graph MinorsDigraphsUnlabelled GraphsUnimodality, Log-Concavity, Real–Rootedness and Beyond; Petter BrándénIntroduction Probabilistic Consequences of Real–RootednessUnimodality and G-NonnegativityLog–Concavity and MatroidsInfinite Log-ConcavityThe Neggers–Stanley ConjecturePreserving Real–RootednessCommon InterleaversMultivariate TechniquesHistorical NotesWords; Dominique Perrin and Antonio RestivoIntroductionPreliminariesConjugacyLyndon wordsEulerian Graphs and De Bruijn CyclesUnavoidable SetsThe Burrows-Wheeler TransformThe Gessel-Reutenauer BijectionSuffix ArraysTilings; James ProppIntroduction and Overview The Transfer Matrix MethodOther Determinant MethodsRepresentation-Theoretic MethodsOther Combinatorial MethodsRelated Topics, and an Attempt at HistorySome Emergent ThemesSoftwareFrontiersLattice Path Enumeration; Christian KrattenthalerIntroduction Lattice Paths Without RestrictionsLinear Boundaries of Slope 1Simple Paths with Linear Boundaries of Rational Slope, ISimple Paths with Linear Boundaries with Rational Slope, IISimple Paths with a Piecewise Linear BoundarySimple Paths with General BoundariesElementary Results on Motzkin and Schroder PathsA continued Fraction for the Weighted Counting of Motzkin PathsLattice Paths and Orthogonal PolynomialsMotzkin Paths in a Strip Further Results for Lattice Paths in the PlaneNon-Intersecting Lattice PathsLattice Paths and Their TurnsMultidimensional Lattice PathsMultidimensional Lattice Paths Bounded by a Hyperplane Multidimensional Paths With a General BoundaryThe Reflection Principle in Full GeneralityQ-Counting Of Lattice Paths and Rogers–Ramanujan IdentitiesSelf-Avoiding WalksCatalan Paths and q; t-enumeration; James HaglundIntroduction to q-Analogues and Catalan NumbersThe q; t-Catalan NumbersParking Functions and the Hilbert SeriesThe q; t-Schr?der PolynomialRational Catalan CombinatoricsPermutation Classes; Vincent VatterIntroductionGrowth Rates of Principal ClassesNotions of StructureThe Set of All Growth RatesParking Functions; Catherine H. YanIntroductionParking Functions and Labeled TreesMany Faces of Parking FunctionsGeneralized Parking FunctionsParking Functions Associated with GraphsFinal RemarksStandard Young Tableaux; Ron Adin and Yuval RoichmanIntroductionPreliminariesFormulas for Thin ShapesJeu de taquin and the RS CorrespondenceFormulas for Classical ShapesMore Proofs of the Hook Length FormulaFormulas for Skew StripsTruncated and Other Non-Classical ShapesRim Hook and Domino Tableauxq-EnumerationCounting Reduced WordsAppendix 1: Representation Theoretic AspectsAppendix 2: Asymptotics and Probabilistic AspectsComputer Algebra; Manuel KauersIntroductionComputer Algebra EssentialsCounting AlgorithmsSymbolic SummationThe Guess-and-Prove ParadigmIndex

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.