A bijection between evil-avoiding and rectangular permutations (Q6197312)

Summary: Evil-avoiding permutations, introduced by \textit{D. Kim} and \textit{L. K. Williams} in [Int. Math. Res. Not. 2023, No. 10, 8143--8211 (2023; Zbl 1525.05192)], arise in the study of the inhomogeneous totally asymmetric simple exclusion process. Rectangular permutations, introduced by \textit{R. Chirivì} et al. in [Transform. Groups 26, No. 4, 1189--1215 (2021; Zbl 1489.14061)], arise in the study of Schubert varieties and Demazure modules. Taking a suggestion of Kim and Williams [loc. cit.], we supply an explicit bijection between evil-avoiding and rectangular permutations in \(S_n\) that preserves the number of recoils. We encode these classes of permutations as regular languages and construct a length-preserving bijection between words in these regular languages. We extend the bijection to another Wilf-equivalent class of permutations, namely the \(1\)-almost-increasing permutations, and exhibit a bijection between rectangular permutations and walks of length \(2n-2\) in a path of seven vertices starting and ending at the middle vertex.