ANALYTIC COMBINATORICS AND SYMBOLIC COMBINATORICS

By C. MIVIK

CONTENTS CHAPTER I COMBINATORIAL STRUCTURES AND ORDINARY GENERATING FUNCTIONS I 1 SYMBOLIC ENUMERATION METHODS I 2 ADMISSIBLE CONSTRUCTIONS AND SPECI?CATIONS I 2 1 BASIC CONSTRUCTIONS I 2 2 THE ADMISSIBILITY THEOREM FOR ORDINARY GENERATING FUNCTIONS I 2 3 CONSTRUCTIBILITY AND COMBINATORIAL SPECI?CATIONS I 2 4 ASYMPTOTIC INTERPRETATION OF COUNTING SEQUENCES I 3 INTEGER COMPOSITIONS AND PARTITIONS I 3 1 COMPOSITIONS AND PARTITIONS I 3 2 INTEGER RELATED CONSTRUCTIONS I 4 WORDS AND REGULAR LANGUAGES I 4 1 REGULAR SPECI?CATIONS I 4 2 FINITE AUTOMATA I 4 3 WORD RELATED CONSTRUCTIONS I 5 TREES AND TREE-LIKE STRUCTURES I 5 1 PLANE TREES I 5 2 NONPLANE TREE I 5 3 TREE RELATED CONSTRUCTIONS I 6 ADDITIONAL CONSTRUCTIONS I 6 1 POINTING AND SUBSTITUTION I 6 2 IMPLICIT STRUCTURES I 7 NOTES CHAPTER II LABELLED STRUCTURES AND EXPONENTIAL GENERATING FUNCTIONS II 1 LABELLED CLASSES AND LABELLED PRODUCT II 2 ADMISSIBLE LABELLED CONSTRUCTIONS II 2 1 LABELLED CONSTRUCTIONS II 2 2 LABELLED VERSUS UNLABELLED? II 3 SURJECTIONS, SET PARTITIONS, AND WORDS II 3 1 SURJECTIONS AND SET PARTITIONS II 3 2 APPLICATIONS TO WORDS AND RANDOM ALLOCATIONS II 4 ALIGNMENTS, PERMUTATIONS, AND RELATED STRUCTURES II 4 1 ALIGNMENTS AND PERMUTATIONS II 4 2 SECOND LEVEL STRUCTURES II 5 LABELLED TREES, MAPPINGS, AND GRAPHS II 5 1 TREES II 5 2 MAPPINGS AND FUNCTIONAL GRAPHS II 5 3 LABELLED GRAPHS II 6 ADDITIONAL CONSTRUCTIONS II 6 1 POINTING AND SUBSTITUTION II 6 2 IMPLICIT STRUCTURES II 6 3 ORDER CONSTRAINTS II 7 NOTES CHAPTER III COMBINATORIAL PARAMETERS AND MULTIVARIATE GENERATING FUNCTIONS III 1 PARAMETERS, GENERATING FUNCTIONS, AND DISTRIBUTIONS III 1 1 MULTIVARIATE GENERATING FUNCTIONS III 1 2 DISTRIBUTIONS, MOMENTS, AND GENERATING FUNCTIONS III 1 3 MOMENT INEQUALITIES III 2 INHERITED PARAMETERS AND ORDINARY MULTIVARIATE GENERATING FUNCTIONS III 3 INHERITED PARAMETERS AND EXPONENTIAL MULTIVARIATE GENERATING FUNCTIONS III 4 RECURSIVE PARAMETERS III 5 “UNIVERSAL” GENERATING FUNCTIONS AND COMBINATORIAL MODELS III 5 1 WORD MODELS III 5 2 TREE MODELS III 6 ADDITIONAL CONSTRUCTIONS III 6 1 POINTING AND SUBSTITUTION III 6 2 ORDER CONSTRAINTS III 6 3 IMPLICIT STRUCTURES III 6 4 INCLUSION-EXCLUSION III 7 EXTREMAL PARAMETERS III 7 1 LARGEST COMPONENTS III 7 2 HEIGHT III 7 3 AVERAGES AND MOMENTS III 8 NOTES