Lehmer Codes and the Reverse-Complement Mapping from (32-1)-Avoiding Permutations to (3-21)-Avoiding Permutations

Andrew Beveridge; Yufan Hu; Yucheng Liu

combinatorics

Lehmer Codes and the Reverse-Complement Mapping from (32-1)-Avoiding Permutations to (3-21)-Avoiding Permutations

arXiv:2607.26900

summary

The paper uses Lehmer codes to model permutations avoiding the vincular patterns 32‑1 and 3‑21 as weighted posets, shows that the maximal elements of these posets are counted by Fibonacci numbers, and establishes a bijection between these maximal sets via the reverse‑complement map.

Abstract

Let $S_{n} (32 - 1)$ and $S_{n} (3 - 21)$ denote the sets of $n$ -permutations avoiding the vincular patterns $32 - 1$ and $3 - 21$ , respectively. Using Lehmer codes, we realize these families as weighted posets $L_{n} (32 - 1)$ and $L_{n} (3 - 21)$ , where the weight of a code is the inversion number of its permutation. We show that the maximal elements of each of these posets, $Max L_{n} (32 - 1)$ and $Max L_{n} (3 - 21)$ , are enumerated by the Fibonacci numbers. We demonstrate that the classical reverse-complement map on permutations restricts to a natural bijection between these two sets of maximal elements, revealing a deep symmetry between their underlying poset structures.

23 pages, 5 figures

Topics & keywords

#permutation patterns #lehmer codes #poset structure #fibonacci enumeration #reverse-complement bijectionvincular patterns32-1 avoidance3-21 avoidanceinversion numberweighted posetreverse-complement mapping