Equivalence classes of ballot paths modulo strings of length 2 and 3

DOI10.1016/J.DISC.2016.05.001zbMATH Open1339.05019arXiv1510.01952OpenAlexW2963095869MaRDI QIDQ294567FDOQ294567

Authors: K. Manes, A. Sapounakis, I. Tasoulas, P. Tsikouras 

Publication date: 16 June 2016

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: Two paths are equivalent modulo a given string $au$, whenever they have the same length and the positions of the occurrences of $au$ are the same in both paths. This equivalence relation was introduced for Dyck paths in cite{BP}, where the number of equivalence classes was evaluated for any string of length 2. In this paper, we evaluate the number of equivalence classes in the set of ballot paths for any string of length 2 and 3, as well as in the set of Dyck paths for any string of length 3.

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

Recommendations

• Equivalence classes of Motzkin paths modulo a pattern of length at most two
• Equivalence classes of Dyck paths modulo some statistics
• Enumeration of Łukasiewicz paths modulo some patterns
• Equivalence classes of skew Dyck paths modulo some patterns
• Dyck paths with catastrophes modulo the positions of a given pattern

zbMATH Keywords

Dyck pathstringballot path

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Fibonacci and Lucas numbers and polynomials and generalizations (11B39)

Cites Work

• The On-Line Encyclopedia of Integer Sequences
• Counting strings at height \(j\) in Dyck paths
• Dyck path enumeration
• Some statistics on Dyck paths
• The statistic ``number of udu's in Dyck paths
• Counting strings in Dyck paths
• Title not available (Why is that?)
• Equivalence classes of Dyck paths modulo some statistics
• Statistics on Dyck paths
• General results on the enumeration of strings in Dyck paths
• Title not available (Why is that?)

Cited In (6)

• Dyck paths with catastrophes modulo the positions of a given pattern
• Bijections from Dyck and Motzkin meanders with catastrophes to pattern avoiding Dyck paths
• Title not available (Why is that?)
• Counting depth zero patterns in ballot paths
• Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata
• Enumeration of Łukasiewicz paths modulo some patterns

Uses Software

• OEIS

This page was built for publication: Equivalence classes of ballot paths modulo strings of length 2 and 3

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