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,\dots ,n\}$. We think of a permutation just as an ordered list. For any $p$ in $S_n$, and for any $i\le n$, let $p\downarrow i$ be the permutation on the set $\{1,2,\dots ,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\le 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)$.