Explicit formulas for enumeration of lattice paths: basketball and the kernel method
| Autor: | Banderier, Cyril, Krattenthaler, Christian, Krinik, Alan, Kruchinin, Dmitry, Kruchinin, Vladimir, Nguyen, David Tuan, Wallner, Michael |
|---|---|
| Přispěvatelé: | Laboratoire d'Informatique de Paris-Nord (LIPN), Université Sorbonne Paris Cité (USPC)-Institut Galilée-Université Paris 13 (UP13)-Centre National de la Recherche Scientifique (CNRS), Fakultät für Mathematik [Wien], Universität Wien, California State Polytechnic University [Pomona] (CAL POLY POMONA), Tomsk State University of Control Systems and Radio Electronics, University of California [Santa Barbara] (UCSB), University of California, Vienna University of Technology (TU Wien), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB) |
| Jazyk: | angličtina |
| Rok vydání: | 2019 |
| Předmět: |
[INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC]
singularity analysis [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] Motzkin paths [MATH.MATH-CV]Mathematics [math]/Complex Variables [math.CV] Lagrange inversion [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] Dyck paths N-algebraic function lattice paths [MATH.MATH-PR]Mathematics [math]/Probability [math.PR] kernel method generating function [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL] [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] FOS: Mathematics analytic combinatorics Mathematics - Combinatorics context-free grammars Combinatorics (math.CO) computer algebra 05A15 (Primary) 05A10 05A16 05A19 (Secondary) |
| Zdroj: | Developments in Mathematics Developments in Mathematics, Springer, 2019, Lattice Path Combinatorics and Applications, pp.78-118 |
| ISSN: | 1389-2177 |
| Popis: | This article deals with the enumeration of directed lattice walks on the integers with any finite set of steps, starting at a given altitude $j$ and ending at a given altitude $k$, with additional constraints such as, for example, to never attain altitude $0$ in-between. We first discuss the case of walks on the integers with steps $-h, \dots, -1, +1, \dots, +h$. The case $h=1$ is equivalent to the classical Dyck paths, for which many ways of getting explicit formulas involving Catalan-like numbers are known. The case $h=2$ corresponds to "basketball" walks, which we treat in full detail. Then we move on to the more general case of walks with any finite set of steps, also allowing some weights/probabilities associated with each step. We show how a method of wide applicability, the so-called "kernel method", leads to explicit formulas for the number of walks of length $n$, for any $h$, in terms of nested sums of binomials. We finally relate some special cases to other combinatorial problems, or to problems arising in queuing theory. AmS-LaTeX, 44 pages; several cosmetic changes |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|