Lattice walks ending on a coordinate hyperplane avoiding backtracking and repeats

DOI10.54550/ECA2022V2S1R3MaRDI QIDQ6097993zbMATH OpenFDO

Authors John Machacek

Publication date 9 June 2023

Published in Enumerative Combinatorics and Applications (Search for Journal in Brave)

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

zbMATH Keywords

formal languagesgenerating functionslattice walksWZ theory

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Asymptotic enumeration (05A16) Symbolic computation of special functions (Gosper and Zeilberger algorithms, etc.) (33F10) Formal languages and automata (68Q45)

Abstract: We work with lattice walks in $mathbb{Z}^{r+1}$ using step set ${pm1}^{r+1}$ that finish with $x_{r+1}=0$. We further impose conditions of avoiding backtracking (i.e. $[v,-v]$) and avoiding consecutive steps (i.e. $[v,v]$) each possibly combined with restricting to the half-space $x_{r+1}geq0$. We find in all cases the generating functions for such walks are algebraic and give explicit formulas for them. We also find polynomial recurrences for their coefficients. From the generating functions we find the asymptotic enumeration of each family of walks considered. The enumeration in special cases includes central binomial coefficients and Catalan numbers as well as relations to enumeration of another family of walks previously studied for which we provide bijection.

Recommendations

• A new system of proof-theoretic ordinal functions
• Investigations on slow versus fast growing: How to majorize slow growing functions nontrivially by fast growing ones
• Functors and ordinal notations. II: A functorial construction of the Bachmann hierarchy
• scientific article; zbMATH DE number 6307926
• Some interesting connections between the slow growing hierarchy and the Ackermann function

Cites work

• A fast algorithm for proving terminating hypergeometric identities
• Analytic combinatorics
• Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata
• Automated counting of restricted Motzkin paths
• Deterministic context free languages
• Differentiably finite power series
• Enumerating a class of lattice paths
• Generating functions for lattice paths with several forbidden patterns
• Gröbner bases and the defining polynomial of a context-free grammar generating function
• scientific article; zbMATH DE number 3932372 (Why is no real title available?)
• scientific article; zbMATH DE number 1735667 (Why is no real title available?)
• scientific article; zbMATH DE number 872231 (Why is no real title available?)
• scientific article; zbMATH DE number 3238653 (Why is no real title available?)
• scientific article; zbMATH DE number 7651040 (Why is no real title available?)
• Lattice path enumeration
• The method of creative telescoping
• The On-Line Encyclopedia of Integer Sequences

Cited in

(2)

• Lattice paths and submonoids of \(\mathbb{Z}^2\)
• The number of [old-time] basketball games with final score \(n\):\(n\) where the home team was never losing but also never ahead by more than \(w\) points

This page was built for publication: Lattice walks ending on a coordinate hyperplane avoiding backtracking and repeats

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