Locally sorted sequences 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
    return True
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):
    if check(perm,k):
        check_count += 1
print(check_count)
Your problem is solved in the paper Spheres of Permutations under the
Infinity Norm &mdash; Permutations with limited displacement by Torleiv Kløve.

See also A002524 and other sequences linked there. I found Kløve's paper by calculating the first few values of A002524 and finding it on the OEIS.