Combinatorics of lattice paths and tree-like structures

Description

Declaration......Page 5 Abstract......Page 7 Zusammenfassung......Page 8 Publications......Page 11 Acknowledgments......Page 13 Contents......Page 15 Introduction......Page 17 1 An invitation to analytic combinatorics and lattice path counting......Page 19 1.1 What is a lattice path?......Page 22 1.2 Analytic combinatorics......Page 25 1.3 Łukasiewicz paths......Page 42 1.4 Marking in combinatorial constructions......Page 49 1.5 Basic parameters of Dyck paths......Page 51 1.6 Properties of general directed lattice paths......Page 54 1.7 Introduction to the combinatorics of trees......Page 58 2.1 Probability distributions......Page 65 2.2 Limit laws......Page 67 2.3 Schemes for generating functions......Page 69 2.4 Symmetric polynomials......Page 76 2.5 Tools from Analytic Combinatorics......Page 78 Lattice paths......Page 83 3.1 The half-normal theorem......Page 85 3.2 Applications to lattice path counting......Page 87 3.3 Proof of Theorem 2.3.9......Page 100 3.4 Conclusion......Page 105 4 The reflection-absorption model for directed lattice paths......Page 107 4.1 The reflection-absorption model......Page 108 4.2 Łukasiewicz walks and excursions......Page 121 4.3 Bridges......Page 128 4.4 Meanders......Page 136 4.5 Moments of the final altitude of meanders......Page 148 4.6 Proofs......Page 155 5 Lattice paths below a line of rational slope......Page 183 5.1 Trees, fractional trees, imaginary trees......Page 186 5.2 Knuth's AofA problem #4......Page 190 5.3 A bijection for lattice paths below a rational slope......Page 191 5.4 Lattice paths of slope 2/5......Page 192 5.5 Asymptotics......Page 195 5.6 Links with Nakamigawa/Tokushige......Page 202 5.7 Duchon's club and other slopes......Page 206 5.8 Conclusion......Page 212 6 Lattice paths with catastrophes......Page 215 6.1 Generating functions......Page 217 6.2 Bijection for Dyck paths with catastrophes......Page 219 6.3 Asymptotics and limit laws......Page 221 6.4 Uniform random generation......Page 232 6.5 Conclusion......Page 234 Trees and Tree-like structures......Page 235 7.1 Decomposing Pólya trees......Page 237 7.2 Main results......Page 239 7.3 The maximal size of a D-forest......Page 241 7.4 D-forests and C-trees......Page 244 7.5 Conclusion and perspectives......Page 249 8 Compacted Binary Trees......Page 251 8.1 Creating a compacted tree......Page 252 8.2 A recurrence relation......Page 255 8.3 Operations on trees......Page 259 8.4 Relaxed binary trees......Page 262 8.5 Compacted binary trees......Page 283 8.6 Connections with Chebyshev polynomials......Page 294 8.7 Conclusion......Page 298 Applications to number theory......Page 301 9 Divisibility of binomial coefficients by powers of primes......Page 303 9.1 A recurrence for the values thetap(j,n)......Page 306 9.2 The polynomials Pj for j>1......Page 308 9.3 Computing the coefficients of Pj......Page 309 9.4 Asymptotic behavior of the coefficients......Page 316 9.5 A simplified recurrence for thetap(j,n)......Page 320 9.6 Divisibility in columns of Pascal's triangle......Page 323 9.7 Proofs......Page 324 Appendix......Page 335 Notation......Page 337 Coefficient asymptotics of standard functions......Page 339 Bibliography......Page 341 Curriculum Vitæ......Page 357 Colophon......Page 363