The vectorial kernel method for walks with longer steps

DOI10.2989/16073606.2021.1925367zbMATH Open1493.05024arXiv2008.02240OpenAlexW3167769630MaRDI QIDQ5089991FDOQ5089991

Authors: Valerie Roitner 

Publication date: 15 July 2022

Published in: Quaestiones Mathematicae (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

asymptotic behaviorgenerating functionslattice pathkernel methodSchröder path

Mathematics Subject Classification ID

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

Cites Work

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

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)