The vectorial kernel method for walks with longer steps

DOI10.2989/16073606.2021.1925367MaRDI QIDQ5089991zbMATH OpenOpenAlexFDO

Authors Valerie Roitner

Publication date 15 July 2022

Published in Quaestiones Mathematicae (Search for Journal in Brave)

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

zbMATH Keywords

asymptotic behaviorgenerating functionslattice pathkernel methodSchröder path

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Asymptotic enumeration (05A16)

Abstract: Asinowski, Bacher, Banderier and Gittenberger (A. Asinowski, A. Bacher, C. Banderier and B. Gittenberger. Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata. Algorithmica, pp. 1-43, 2019.) recently developed the vectorial kernel method - a powerful extension of the classical kernel method that can be used for paths that obey constraints that can be described by finite automata, e.g. avoid a fixed pattern, avoid several patterns at once, stay in a horizontal strip and many others more. However, they only considered walks with steps of length one. In this paper we will generalize their results to walks with longer steps. We will also give some applications of this extension and prove a conjecture about the asymptotic behavior of the expected number of ascents in Schroeder paths.

Recommendations

• Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata
• On the kernel curves associated with walks in the quarter plane
• Enumeration and asymptotics for the area of lattice paths
• Asymptotics of lattice walks via analytic combinatorics in several variables
• Basic analytic combinatorics of directed lattice paths

Cites work

• scientific article; zbMATH DE number 986989 (Why is no real title available?)
• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• scientific article; zbMATH DE number 2046067 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• Analytic combinatorics
• Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata
• Basic analytic combinatorics of directed lattice paths
• Combinatorics of RNA structures with pseudoknots
• Dual-pivot quicksort: optimality, analysis and zeros of associated lattice paths
• Formulae and asymptotics for coefficients of algebraic functions
• Generating functions for lattice paths with several forbidden patterns
• Lattice paths of slope \(2/5\)
• Poland-Scheraga models and the DNA denaturation transition
• Polynomial equations with one catalytic variable, algebraic series and map enumeration
• Schröder paths and pattern avoiding partitions
• The Dyck pattern poset
• Walks with small steps in the quarter plane
• Walks, walls, wetting, and melting

This page was built for publication: The vectorial kernel method for walks with longer steps

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