On the generating functions of pattern-avoiding Motzkin paths

DOI10.1016/J.JSC.2022.02.006zbMATH Open1487.05020arXiv2108.03037OpenAlexW4214829125WikidataQ113869804 ScholiaQ113869804MaRDI QIDQ2133921FDOQ2133921

Antonio Bernini, Christian Bean, L. Ferrari, Matteo Cervetti

Publication date: 5 May 2022

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Abstract: Using a recursive approach, we show that the generating function for sets of Motzkin paths avoiding a single (not necessarily consecutive) pattern is rational over $x$ and the Catalan generating function $C(x)=frac1-sqrt1-4x^{2}2x^2$, where $x$ keeps track of the length of the path. Moreover, an algorithm is provided for finding the generating function in the more general case of an arbitrary set of patterns. In addition, this algorithm allows us to find a combinatorial specification for pattern-avoiding Motzkin paths, which can be used not only for enumeration, but also for exhaustive and random generation.

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

zbMATH Keywords

generating functionlattice pathpatternMotzkin pathcombinatorial specification

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Factorials, binomial coefficients, combinatorial functions (05A10)

Cites Work

• Counting strings in Dyck paths
• Motzkin numbers
• The Dyck pattern poset
• Generating functions for lattice paths with several forbidden patterns
• Enumerative results on the Schröder pattern poset
• Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (6)

• A bijection for some paths on the slit plane
• Generating functions for lattice paths with several forbidden patterns
• Motzkin paths, Motzkin polynomials and recurrence relations
• Raney numbers, threshold sequences and Motzkin-like paths
• Fibonacci and Catalan paths in a wall
• Pattern avoiding partitions and Motzkin left factors

Uses Software

• OEIS

This page was built for publication: On the generating functions of pattern-avoiding Motzkin paths

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