On a conjecture on pattern-avoiding machines

Abstract

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 $\sigma$-machine $s\circ s_{\sigma }$ as a generalization of West's $2$-stack-sorting-map $s\circ s$. As a further generalization, in 2021, Baril, Cerbai, Khalil, and Vajnovski introduced the $(\sigma ,\tau )$-machine $s\circ s_{\sigma ,\tau }$ and enumerated $|\Sort_{n}(σ,τ)|$ -- the number of permutations in $S_n$ that are mapped to the identity by the $(\sigma ,\tau )$-machine -- for six pairs of length $3$ permutations $(\sigma ,\tau )$. In this work, we settle a conjecture by Baril, Cerbai, Khalil, and Vajnovski on the only remaining pair of length $3$ patterns $(\sigma ,\tau )=(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.