Let $S=s_1,\ldots,s_n$ be a sequence and $p$ be a permutation on the indices of $S$ such that $p$ sorts $S$.
Define a sequence to be locally sorted with degree $k$ if $\forall s_i \in S |p(i) - i | \leq k$.
How many locally sorted sequences of degree $k$ are there for $n$ elements? Hopefully, there will be a better approach than "enumerate all possible sequences and check each one".
I wasn't sure how to approach this problem, so I tried proofing results for various values of $k$. I solved this for $k=1$; it's just a Fibonacci sequence. $k=2$ is a lot more difficult to me. I keep overcounting.
For handiness, here's some Python code to use when checking results:
from itertools import permutations
def check(seq, k):
for i in range(0, len(seq)):
index = i+1
if abs(seq[i] - index) > k: return False
n = 5
k = 2
orig = [ i+1 for i in range(0,n) ] # easier if we use sequences of integers
check_count = 0
for perm in permutations(orig):
check_count += 1