Cycles in the graph of overlapping permutations avoiding barred patterns
Summary: As a variation of De Bruijn graphs on strings of symbols, the graph of overlapping permutations has a directed edge \(\pi(1)\pi(2)\ldots \pi(n+1)\) from the standardization of \(\pi(1)\pi(2)\ldots \pi(n)\) to the standardization of \(\pi(2)\pi(3)\ldots \pi(n+1)\). In this paper, we consider the enumeration of \(d\)-cycles in the subgraph of overlapping \((231, 4\bar{1}32)\)-avoiding permutations. To this end, we introduce the notions of marked Motzkin paths and marked Riordan paths, where a marked Motzkin (resp. Riordan) path is a Motzkin (resp. Riordan) path in which exactly one step before the leftmost return point is marked. We show that the number of closed walks of length \(d\) in the subgraph of overlapping \((231, 4\bar{1}32)\)-avoiding permutations are closely related to the number of marked Motzkin paths and that of marked Riordan paths. ~By establishing bijections, we get the enumerations of marked Motzkin paths and marked Riordan paths. As a corollary, we provide bijective proofs of two identities involving Catalan numbers in answer to the problem posed by \textit{R. Ehrenborg} et al. [J. Comb. Theory, Ser. A 129, 1--18 (2015; Zbl 1302.05081)]. Moreover, we get the enumerations of \((231, 4\bar{1}32)\)-avoiding affine permutations and \((312, 32\bar{4}1)\)-avoiding affine permutations.
- Number of cycles in the graph of 312-avoiding permutations
- Number of cycles in the graph of 312-avoiding permutations
- Enumerating cycles in the graph of overlapping permutations
- Permutations weakly avoiding barred patterns and combinatorial bijections to generalized Dyck and Motzkin paths
- Pattern-restricted permutations composed of 3-cycles
- A spectral approach to consecutive pattern-avoiding permutations
- Affine permutations of type \(A\)
- Catalan, Motzkin, and Riordan numbers
- Dyck path enumeration
- Enumerating pattern avoidance for affine permutations
- From Motzkin to Catalan permutations
- Handbook of Enumerative Combinatorics
- scientific article; zbMATH DE number 2024859 (Why is no real title available?)
- scientific article; zbMATH DE number 2107707 (Why is no real title available?)
- scientific article; zbMATH DE number 3422259 (Why is no real title available?)
- Juggling and applications to \(q\)-analogues
- Motzkin numbers
- Motzkin paths and reduced decompositions for permutations with forbidden patterns
- Number of cycles in the graph of 312-avoiding permutations
- On uniquely k-determined permutations
- Patterns in permutations and words.
- Riordan paths and derangements
- Some combinatorial properties of Schubert polynomials
- Universal cycles for combinatorial structures
- Enumerating cycles in the graph of overlapping permutations
- Encoding labelled \(p\)-Riordan graphs by words and pattern-avoiding permutations
- Number of cycles in the graph of 312-avoiding permutations
- Number of cycles in the graph of 312-avoiding permutations
- Some statistics on the hypercubes of Catalan permutations
This page was built for publication: Cycles in the graph of overlapping permutations avoiding barred patterns
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q727057)
