Maximal Lehmer Codes for Permutations with Classical and Consecutive 321-Avoidance

Abstract

Let $S_n(321)$ and $S_n(\underline{321})$ denote the sets of $n$-permutations avoiding the classical pattern $321$ and the consecutive pattern $\underline{321}$, respectively. Permutations are in bijection with Lehmer codes, a type of inversion sequence. Using Lehmer codes, we create the corresponding weighted posets $L_n(321)$ and $L_n(\underline{321})$, where the weight of a code is the inversion number of its permutation. We show that there are $2^{n-2}$ maximal elements of $L_n(321)$, while the maximal elements of $L_n(\underline{321})$ are enumerated by the Padovan numbers. We also show that when $n$ is even, each of these posets has a unique maximum weight element, and that when $n$ is odd, there are two maximum weight elements. These maximum weight Lehmer codes correspond to the pattern avoiding permutations with maximum inversion number.

arXiv comment19 pages, 5 figures