Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata
From MaRDI portal
Publication:2292858
DOI10.1007/S00453-019-00623-3zbMath1437.68091OpenAlexW2980005048MaRDI QIDQ2292858
Axel Bacher, Andrei Asinowski, Cyril Banderier, Bernhard Gittenberger
Publication date: 6 February 2020
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-019-00623-3
generating functionsMarkov chainsasymptotic analysiskernel methodlattice pathsMotzkin pathsWiener-Hopf factorizationfinite automataautocorrelationDyck pathspattern avoidancepushdown automataGaussian limit lawŁukasiewicz pathsBorges' theorem
Exact enumeration problems, generating functions (05A15) Formal languages and automata (68Q45) Other combinatorial number theory (11B75) Asymptotic enumeration (05A16)
Related Items (12)
On the generating functions of pattern-avoiding Motzkin paths ⋮ Automated counting of restricted Motzkin paths ⋮ Computational aspects of sturdy and flimsy numbers ⋮ The vectorial kernel method for walks with longer steps ⋮ Universal asymptotic properties of positive functional equations with one catalytic variable ⋮ Lattice walks ending on a coordinate hyperplane avoiding backtracking and repeats ⋮ Generating functions for lattice paths with several forbidden patterns ⋮ Structure of the space of taboo-free sequences ⋮ Pattern statistics in faro words and permutations ⋮ Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata ⋮ Counting embeddings of rooted trees into families of rooted trees ⋮ Number of prefixes in trace monoids: clique polynomials and dependency graphs
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Equivalence classes of ballot paths modulo strings of length 2 and 3
- The Dyck pattern poset
- Strings of length 3 in grand-Dyck paths and the Chung-Feller property
- Statistics on bargraphs viewed as cornerless Motzkin paths
- The concrete tetrahedron. Symbolic sums, recurrence equations, generating functions, asymptotic estimates
- Identities for the number of standard Young tableaux in some \((k,l)\)-hooks
- Weakly directed self-avoiding walks
- Symmetric circular matchings and RNA folding
- On the probability that certain compositions have the same number of parts
- Generalized Dyck paths
- Counting humps in Motzkin paths
- 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]
- On directed lattice paths with vertical steps
- Counting surfaces. CRM Aisenstadt chair lectures
- Pattern avoiding ballot paths and finite operator calculus
- Circular digraph walks, \(k\)-balanced strings, lattice paths and Chebychev polynomials
- A new enumerative property of the Narayana numbers
- Subdivision des nombres de Narayana suivant deux paramètres supplémentaires. (Subdivision of Narayana numbers following two supplementary parameters)
- Combinatorial aspects of continued fractions
- String overlaps, pattern matching, and nontransitive games
- Enumeration of plane trees by branches and endpoints
- On some new sequences generalizing the Catalan and Motzkin numbers
- Underdiagonal lattice paths with unrestricted steps
- On the enumeration and generation of generalized Dyck words
- Basic analytic combinatorics of directed lattice paths
- Analytic combinatorics of lattice paths with forbidden patterns: enumerative aspects
- A generalized Goulden-Jackson cluster method and lattice path enumeration
- Enumeration of Łukasiewicz paths modulo some patterns
- Counting consecutive pattern matches in \(\mathcal{S}_n(132)\) and \(\mathcal{S}_n(123)\)
- A bijection between ordered trees and 2-Motzkin paths and its many consequences
- The statistic ``number of udu's in Dyck paths
- Skew Dyck paths, area, and superdiagonal bargraphs
- Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata
- Explicit formulas for enumeration of lattice paths: basketball and the kernel method
- The kernel method for lattice paths below a line of rational slope
- Paired patterns in lattice paths
- Motzkin subposets and Motzkin geodesics in Tamari lattices.
- Vertically constrained Motzkin-like paths inspired by bobbin lace
- Combinatorics of RNA structures with pseudoknots
- Counting humps and peaks in generalized Motzkin paths
- Counting strings in Dyck paths
- Polynomial equations with one catalytic variable, algebraic series and map enumeration
- Why Delannoy numbers?
- Enumeration of generalized lattice paths by string types, peaks, and ascents
- Binary strings without zigzags
- Discrete excursions
- Counting Depth Zero Patterns in Ballot Paths
- Visits to Level r by Dyck Paths
- Permutations avoiding 1324 and patterns in Łukasiewicz paths
- Lattice Path Enumeration
- Ballot Paths Avoiding Depth Zero Patterns
- Nonleaf Patterns in Trees: Protected Nodes and Fine Numbers
- Dyck Paths with Peaks Avoiding or Restricted to a Given Set
- Combinatorics of $\lambda$-terms: a natural approach
- Quadrant marked mesh patterns in 123-avoiding permutations
- Ascents in Non-Negative Lattice Paths
- More Patterns in Trees: Up and Down, Young and Old, Odd and Even
- Formulae and Asymptotics for Coefficients of Algebraic Functions
- Rational and algebraic series in combinatorial enumeration
- On the synchronizing properties of certain prefix codes
- On context-free languages and push-down automata
This page was built for publication: Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata
