Constrained Underdiagonal Paths and pattern Avoiding Permutations
Andrea Frosini, Veronica Guerrini, Simone Rinaldi · Preprints.org · 2024
We show a simple bijection $P$ between permutations $S_n$ of length $n$ and underdiagonal paths of size $n$, the last being lattice paths made of up $U=(1,1)$, down $D=(1,-1)$, west $W=(-1,1)$ steps, running from $(0,0)$ to $(2n,0)$, and such that: (1) the path is weakly bounded by the lines $y=0$ and $x=y$; (2) a $D$ (resp. $W$) step cannot be followed by a $W$ (resp. $D$) step. The aim of this paper is to study and enumerate families of underdiagonal paths which are defined by restricting the bijection $P$ to subclasses of $S_n$ avoiding some vincular patterns. For a given pattern $\tau$, let $S(\tau)$ be the family of permutations avoiding $\tau$, and $P(\tau)$ the family of underdiagonal paths corresponding to permutations in $S(\tau)$, precisely $P(\tau)=\{ P(\pi): \pi \in S(\tau) \}.$ We will consider patterns $\tau$ of length $3$ and $4$, and, when it is possible, we will provide a characterization of the underdiagonal paths of $P(\tau)$ in terms of geometrical constrains, or equivalently, the avoidance of some factors. Finally, we will provide a recursive growth of these families by means of generating trees and then their enumerative sequence.