Counting crucial permutations with respect to monotone patterns

2022/08/29 by Yunseo Choi, Choi, Yunseo · 1 citation
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Bayesian Methods and Mixture Models #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics

paper · pdf · doi:10.48550/arxiv.2208.13469

openalex publication_date 2022/08/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Recently, Avgustinovich, Kitaev, and Taranenko defined five types of (k, ℓ)-crucial permutations, which are maximal permutations that do not contain an increasing subsequence of length k or a decreasing subsequence of length ℓ. Further, Avgustinovich, Kitaev, and Taranenko began the enumeration of the (k, ℓ)-crucial permutations of the minimal length and the next minimal length and the (k, 3)-crucial permutations of all lengths for each of the five types of (k,ℓ)-crucial permutations. In this paper, we complete the enumeration that Avgustinovich, Kitaev, and Taranenko began.

Cited by

• On P-crucial square-free permutations

Related

• On five types of crucial permutations with respect to monotone patterns
• Permutations avoiding sets of patterns with long monotone subsequences
• Permutations, cycles, and the pattern 2-13
• Some open problems on permutation patterns
• Crucial and bicrucial permutations with respect to arithmetic monotone patterns