Pattern avoidance in circular permutations

2002/10/01 by David Callan, Callan, David · 1 citation
Biochemistry, Genetics and Molecular Biology · Mathematics · #05A15 #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #DNA and Biological Computing #FOS: Mathematics #Genome Rearrangement Algorithms #math.CO #msc:05A15

paper · pdf · doi:10.48550/arxiv.math/0210014

LaTeX

arxiv created 2002/10/01 · openalex publication_date 2002/10/01 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Circular permutations on 1,2,...,n that avoid a given pattern correspond to ordinary (linear) permutations that end with n and avoid all cyclic rotations of the pattern. Three letter patterns are all but unavoidable in circular permutations and here we give explicit formulas for the number of circular permutations that avoid one four letter pattern. In the three essentially distinct cases, the counts are as follows: the Fibonacci number F_2n-3 for the pattern 1324, 2^n-1-(n-1) for 1342, and 2ⁿ+1-2n-nchoose3 for 1234.

Cited by

• Consecutive patterns in circular permutations

Related

• Pattern avoidance in permutations and their rotations
• Permutations avoiding a nonconsecutive instance of a 2- or 3-letter pattern
• Permutations Containing and Avoiding 123 and 132 Patterns
• Enumerating circular permutations avoiding the vincular pattern 23 4 1
• Pattern avoidance in compositions and powers of permutations