Determining a Permutation From its Set of Reductions

Abstract

For any positive integer \(n\), let \(S_n\), denote the set of all permutations of the set \(\{1,2,\ldots,n\}\). We think of a permutation just as an ordered list. For any \(p\) in \(S_n\), and for any \(i \leq n\), let \(p \downarrow i\) be the permutation on the set \(\{1,2,\ldots,n – 1\}\) obtained from \(p\) as follows: delete \(i\) from \(p\) and then subtract \(1\) in place from each of the remaining entries of \(p\) which are larger than \(i\). For any \(p\) in \(S_n\), we let \(R(p) = \{q \in S_{n-1} : g = p \downarrow i \;\text{for some} \;i \leq n\}\), the set of reductions of \(p\). It is shown that, for \(n > 4\), any \(p\) in \(S_n\), is determined by its set of reductions \(R(p)\).