Abstract:
Lehmer's transformation of the GS-permutations introduced by I. Gessel and R. Stanley is considered. It is proved that the iteration of Lehmer's transformation of all GS-permutations of order $r\geq1$ leads to the set of all 312-avoiding GS-permutations of order $r$ and thus gives new characterization of these permutations. It is shown that the statistics $\mathrm{rise}$ and $\mathrm{imal}$ on the set of the 312-avoiding GS-permutations of order $r$ have the same distribution. A simple relation connecting the inverses of the generating function of the Narayana polynomials of order $r$ and the exponential generating function of Euler's polynomials of order $r$ is found.