Permutations with exactly one copy of a decreasing pattern of length k

2021/01/01 by Miklós Bóna, Bóna, Miklós, Alexander Burstein +1
Computer Science · Mathematics · #05A05 #Advanced Combinatorial Mathematics #Advanced Mathematical Identities #Combinatorics (math.CO) #FOS: Mathematics #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2101.00332

openalex publication_date 2021/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We construct an injection from the set of permutations of length n that contain exactly one copy of the decreasing pattern of length k to the set of permutations of length n+2 that avoid that pattern. We then prove that the generating function counting the former is not rational, and in the case when k is even and k≥ 4, it is not even algebraic. We extend our injection and our nonrationality result to a larger class of patterns.

Related

• Permutations with a fixed number of occurrences of a monotone pattern
• Most principal permutation classes have nonrational generating functions
• Permutations avoiding bipartite partially ordered patterns have a regular insertion encoding
• On the Best Upper Bound for Permutations Avoiding A Pattern of a Given Length
• Pattern Avoiding Permutations Enumerated by Inversions