xvi TABLE OF CONTENTS CHAPTER FOUR:ASYMPTOTIC APPROXIMATIONS 151 4.1 Notation for Asymptotic Approximations 153 4.2 Asymptotic Expansions 160 4.3 Manipulating Asymptotic Expansions 169 4.4 Asymptotic Approximations of Finite Sums 176 4.5 Euler-Maclaurin Summation 179 4.6 Bivariate Asymptotics 187 4.7 Laplace Method 203 4.8“Normal'"Examples from the Analysis of Algorithms 207 4.9“Poisson"Examples from the Analysis of Algorithms 211 CHAPTER FIVE:ANALYTIC COMBINATORICS 219 5.1 Formal Basis 220 5.2 Symbolic Method for Unlabelled Classes 221 5.3 Symbolic Method for Labelled Classes 229 5.4 Symbolic Method for Parameters 241 5.5 Generating Function Coefficient Asymptotics 247 CHAPTER SIX:TREES 257 6.1 Binary Trees 258 6.2 Forests and Trees 261 6.3 Combinatorial Equivalences to Trees and Binary Trees 264 6.4 Properties of Trees 272 6.5 Examples of Tree Algorithms 277 6.6 Binary Search Trees 281 6.7 Average Path Length in Catalan Trees 287 6.8 Path Length in Binary Search Trees 293 6.9 Additive Parameters of Random Trees 297 6.10 Height 302 6.11 Summary of Average-Case Results on Properties of Trees 310 6.12 Lagrange Inversion 312 6.13 Rooted Unordered Trees 315 6.14 Labelled Trees 327 6.15 Other Types of Trees 331 www.it-ebooks.infoxvi T ō Ŏ Ř ő ś Œ C ś Ś Š ő Ś Š ş CŔōŜŠőŞ FśšŞ: AşťřŜŠśŠ ŕŏ AŜŜŞśŤ ŕřōŠ ඦş 151 4.1 Notation for Asymptotic Approximations 153 4.2 Asymptotic Expansions 160 4.3 Manipulating Asymptotic Expansions 169 4.4 Asymptotic Approximations of Finite Sums 176 4.5 Euler-Maclaurin Summation 179 4.6 Bivariate Asymptotics 187 4.7 Laplace Method 203 4.8 “Normal” Examples from the Analysis of Algorithms 207 4.9 “Poisson” Examples from the Analysis of Algorithms 211 CŔōŜŠőŞ F ŕŢő: AŚōŘťŠ ŕŏ CśřŎ ŕŚōŠśŞ ŕŏş 219 5.1 Formal Basis 220 5.2 Symbolic Method for Unlabelled Classes 221 5.3 Symbolic Method for Labelled Classes 229 5.4 Symbolic Method for Parameters 241 5.5 Generating Function Coefficient Asymptotics 247 CŔōŜŠőŞ S ŕŤ: TŞőőş 257 6.1 Binary Trees 258 6.2 Forests and Trees 261 6.3 Combinatorial Equivalences to Trees and Binary Trees 264 6.4 Properties of Trees 272 6.5 Examples of Tree Algorithms 277 6.6 Binary Search Trees 281 6.7 Average Path Length in Catalan Trees 287 6.8 Path Length in Binary Search Trees 293 6.9 Additive Parameters of Random Trees 297 6.10 Height 302 6.11 Summary of Average-Case Results on Properties of Trees 310 6.12 Lagrange Inversion 312 6.13 Rooted Unordered Trees 315 6.14 Labelled Trees 327 6.15 Other Types of Trees 331 www.it-ebooks.info