On a Conjecture on Pattern-Avoiding Machines

Let s be West’s stack-sorting map, and let s_T be the generalized stack-sorting map, where instead of being required to increase, the stack avoids subpermutations that are order-isomorphic to any permutation in the set T. In 2020, Cerbai, Claesson, and Ferrari introduced the σ-machine s∘s_σ as a generalization of West’s 2-stack-sorting-map s∘s. As a further generalization, in 2021, Baril, Cerbai, Khalil, and Vajnovski introduced the (σ,τ)-machine s∘s_σ,τ and enumerated Sort_n(σ,τ)—the number of permutations in S_n that are mapped to the identity by the (σ,τ)-machine—for six pairs of length 3 permutations (σ,τ). In this work, we settle a conjecture by Baril, Cerbai, Khalil, and Vajnovski on the only remaining pair of length 3 patterns (σ,τ)=(132,321) for which |Sort_n(σ,τ)| appears in the OEIS. In addition, we enumerate Sort_n(123,321), which does not appear in the OEIS, but has a simple closed form.