Pattern avoidance of [4,k]-pairs in circular permutations

DOI10.1016/J.AAM.2022.102346MaRDI QIDQ2134002zbMATH OpenOpenAlexFDO

Authors Krishna Menon, Anurag Singh

Publication date 5 May 2022

Published in Advances in Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

circular permutationpattern avoidanceWilf equivalence

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Combinatorial identities, bijective combinatorics (05A19)

Abstract: The study of pattern avoidance in linear permutations has been an active area of research for almost half a century now, starting with the work of Knuth in 1973. More recently, the question of pattern avoidance in circular permutations has gained significant attention. In 2002-03, Callan and Vella independently characterized circular permutations avoiding a single permutation of size $4$. Building on their results, Domagalski et al. studied circular pattern avoidance for multiple patterns of size $4$. In this article, our main aim is to study circular pattern avoidance of $[4,k]$-pairs, i.e., circular permutations avoiding one pattern of size 4 and another of size $k$. We do this by using well-studied combinatorial objects to represent circular permutations avoiding a single pattern of size $4$. In particular, we obtain upper bounds for the number of Wilf equivalence classes of $[4,k]$-pairs. Moreover, we prove that the obtained bound is tight when the pattern of size $4$ in consideration is $[1342]$. Using ideas from our general results, we also obtain a complete characterization of the avoidance classes for $[4,5]$-pairs.

Recommendations

• Cyclic pattern containment and avoidance
• Pattern avoidance in permutations: Linear and cyclic orders
• Vincular pattern avoidance on cyclic permutations
• Finite transition matrices for permutations avoiding pairs of length four patterns
• Partial permutations avoiding pairs of patterns

Cites work

• Combinatorics of permutations
• Combinatorics: the art of counting
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3492580 (Why is no real title available?)
• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• On multiple pattern avoiding set partitions
• Pattern avoidance in permutations: Linear and cyclic orders
• Pattern containment in circular permutations
• Patterns in colored circular permutations
• Patterns in permutations and words.
• Permutation pattern matching in (213,231)-avoiding permutations
• Restricted permutations
• Spherical Schubert varieties and pattern avoidance
• Vincular pattern avoidance on cyclic permutations
• When is a Schubert variety Gorenstein?

Cited in

(7)

• Finite transition matrices for permutations avoiding pairs of length four patterns
• Cyclic pattern containment and avoidance
• On a question of Li concerning an uncounted class of circular permutations
• Subsequence frequency in binary words
• Pattern avoidance in partial permutations
• Dyck paths, binary words, and Grassmannian permutations avoiding an increasing pattern
• The circular balancing problem

Describes a project that uses

Uses Software

• SageMath
• OEIS

This page was built for publication: Pattern avoidance of \([4,k]\)-pairs in circular permutations

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