Counting crucial permutations with respect to monotone patterns

Abstract

Recently, Avgustinovich, Kitaev, and Taranenko defined five types of $(k,\ell )-$crucial permutations, which are maximal permutations that do not contain an increasing subsequence of length $k$ or a decreasing subsequence of length $\ell$. Further, Avgustinovich, Kitaev, and Taranenko began the enumeration of the $(k,\ell )-$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,\ell )-$crucial permutations. In this paper, we complete the enumeration that Avgustinovich, Kitaev, and Taranenko began.