Iterating the Lehmer code on inversion sequences: Catalan fixed points and finite stabilization

Abstract

We study an operator $\Theta$ on finite integer sequences, where $\Theta (\sigma {)}_i$ counts the entries to the left of ${\sigma }_i$ that are strictly smaller than ${\sigma }_i$. This operator is a variant of the so-called Lehmer code. For every sequence $\sigma$, the image $\Theta (\sigma )$ is an inversion sequence, and the restriction of $\Theta$ to permutations of $[0,n-1]$ is a bijection onto inversion sequences of length $n$. We characterize the fixed points of $\Theta$ by avoidance of the pattern $101$ together with a saturation condition, prove that they are counted by the Catalan numbers, and give an explicit recursive bijection with Dyck paths. We also show that the sequences whose first $\Theta$-image is fixed are precisely those avoiding both $101$ and $201$. Finally, we prove finite stabilization for all inversion sequences, exhibit a family attaining the maximal stabilization time, and show that the second stabilization level is not closed under classical patterns.