Enumerating Anchored Permutations with Bounded Gaps

Abstract

Say that a permutation of $1,2,\dots ,n$ is \textit{$k$-bounded} if every pair of consecutive entries in the permutation differs by no more than $k$. Such a permutation is \textit{anchored} if the first entry is $1$ and the last entry is $n$. We show that the generating function for the enumeration of $k$-bounded anchored permutations is always rational, mirroring the known result on (non-anchored) $k$-bounded permutations due to Avgustinovich and Kitaev. We then explicitly determine the recursive formulas of minimal depth for the number of anchored $k$-bounded permutations of $n$ for $k=2$ and $k=3$, resolving a conjecture listed on the Online Encyclopedia of Integer Sequences (entry A249665). We additionally show that the number of anchored $k$-bounded permutations of $n$ is asymptotically $O\left(k^n\right)$ as a function of $n$ for a given $k$.

This is an updated version including two new results: the rationality of the generating function for all k, and asymptotic bounds on the number of k-bounded permutations of n