Restricted Stacks as Functions

Katalin Berlow

Published 2020-08-03Version 1

The stack sort algorithm has been the subject of extensive study over the years. In this paper we explore a generalized version of this algorithm where instead of avoiding a single decrease, the stack avoids a set $T$ of permutations. We let $s_T$ denote this map. We classify for which sets $T$ the map $s_T$ is bijective. A corollary to this answers a question of Baril, Khalil, and Vajnovszki about stack sort composed with $s_{\{\sigma,\tau\}}$, known as the $(\sigma,\tau)$-machine. This fully classifies for which $\sigma$ and $\tau$ the preimage of the identity under the $(\sigma,\tau)$-machine is counted by the Catalan numbers. We also prove that the number of preimages of a permutation under the map $s_T$ is bounded by the Catalan numbers, with a shift of indices. For $T$ of size 1, we classify exactly when this bound is sharp. We also explore the periodic points and maximum number of preimages of various $s_T$ for $T$ containing two length $3$ permutations.