Publication:2328846

DOI10.1007/978-3-030-11102-1_6zbMATH Open1422.05007arXiv1609.06473OpenAlexW2963222432MaRDI QIDQ2328846FDOQ2328846

Yanyan Li

Publication date: 16 October 2019

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1609.06473

zbMATH Keywords

computer algebragenerating functioncontext-free grammarsDyck pathsLagrange inversionlattice pathskernel methodsingularity analysisanalytic combinatoricsMotzkin paths\(\mathbb{N}\)-algebraic function

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Factorials, binomial coefficients, combinatorial functions (05A10) Asymptotic enumeration (05A16) Combinatorial identities, bijective combinatorics (05A19)

Cited In (8)

• Bijections between directed animals, multisets and Grand-Dyck paths
• The research and progress of the enumeration of lattice paths
• Analysis of bidirectional ballot sequences and random walks ending in their maximum
• Pseudo-involutions in the Riordan group
• Symmetric Fibonaccian distributive lattices and representations of the special linear Lie algebras
• Knight's paths towards Catalan numbers
• Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata
• Enumerative combinatorics of \textit{XX0} Heisenberg chain

Uses Software

• gfun

This page was built for publication: Explicit formulas for enumeration of lattice paths: basketball and the kernel method

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2328846)