On 132-Avoiding Permutations with an Adjacency Constraint

We study permutations in $S_n$ that simultaneously avoid the pattern $132$ and satisfy the adjacency bound $\mathrm{\mid }{\pi }_{i+1}-{\pi }_i\mathrm{\mid }\le m$ for all $i$, denoting their number by $A_n^{(m)}$. This combination of a global pattern restriction and a local bounded-difference condition produces a strong structural collapse: whereas unrestricted $132$-avoiding permutations are counted by the Catalan numbers with exponential growth rate $4$, the adjacency constraint forces the maximum element $n$ to occupy only positions in $\{1,2,\dots ,m\}\cup \{n\}$. We give a complete solution for $m=2$ by partitioning the class according to the position of the maximum element. This yields explicit recurrences and a rational generating function, from which we derive asymptotic growth of the form $A_n^{(2)}\sim C{\alpha }^n$ with $\alpha \approx 1.4656$. We conjecture that for each fixed $m$, the class admits a finite-state structural decomposition leading to linear recurrences with constant coefficients and rational generating functions, with growth constants increasing to $4$.