Vincular pattern avoidance on cyclic permutations

DOI10.54550/ECA2022V2S4PP3zbMATH Open1512.05017arXiv2107.12353MaRDI QIDQ6156004FDOQ6156004

Authors: Rupert Li 

Publication date: 9 June 2023

Published in: Enumerative Combinatorics and Applications (Search for Journal in Brave)

Abstract: Pattern avoidance for permutations has been extensively studied, and has been generalized to vincular patterns, where certain elements can be required to be adjacent. In addition, cyclic permutations, i.e., permutations written in a circle rather than a line, have been frequently studied, including in the context of pattern avoidance. We investigate vincular pattern avoidance on cyclic permutations. In particular, we enumerate many avoidance classes of sets of vincular patterns of length 3, including a complete enumeration for all single patterns of length 3. Further, several of the avoidance classes corresponding to a single vincular pattern of length 4 are enumerated by the Catalan numbers. We then study more generally whether sets of vincular patterns of an arbitrary length $k$ can be avoided for arbitrarily long cyclic permutations, in particular investigating the boundary cases of minimal unavoidable sets and maximal avoidable sets.

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

Recommendations

• Pattern avoidance in permutations: Linear and cyclic orders
• Cyclically consecutive permutation avoidance
• Pattern avoidance of generalized permutations
• Pattern avoidance in partial permutations
• Enumerating pattern avoidance for affine permutations
• On pattern avoiding alternating permutations
• Pattern avoidance in poset permutations
• Avoiding patterns in irreducible permutations
• Pattern avoiding meandric permutations
• On pattern avoiding indecomposable permutations

zbMATH Keywords

pattern avoidancecyclic permutationsvincular patterns

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

Cites Work

• Generalized permutation patterns and a classification of the Mahonian statistics
• A survey of alternating permutations
• Patterns in permutations and words.
• The patterns of permutations
• Counting strings in Dyck paths
• Classification of bijections between 321- and 132-avoiding permutations
• Generalized pattern avoidance
• Non-overlapping partitions, continued fractions, Bessel functions and a divergent series
• Refined enumeration of permutations sorted with two stacks and a \(D_8\)-symmetry
• Partial and complete cyclic orders
• Enumeration schemes for permutations avoiding barred patterns
• Counting Arrangements of 1's and -1's
• Generalized permutation patterns -- a short survey
• A proof of Julian West's conjecture that the number of two-stack-sortable permutations of length \(n\) is \(2(3n)\)!/(\((n+1)\)!\((2n+1)\)!)
• Multi-static enumeration of two-stack sortable permutations
• Cyclic ordering is NP-complete
• Restricted partitions and generalized Catalan numbers
• Extensions of partial cyclic orders, Euler numbers and multidimensional boustrophedons
• Title not available (Why is that?)
• Cyclically Consecutive Permutation Avoidance

Cited In (6)

• Enumeration schemes for vincular patterns
• Title not available (Why is that?)
• Pattern-restricted permutations composed of 3-cycles
• Cyclic and lift closures for \(k \ldots 21\)-avoiding permutations
• Cyclic pattern containment and avoidance
• Pattern avoidance of \([4,k]\)-pairs in circular permutations

This page was built for publication: Vincular pattern avoidance on cyclic permutations

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