# 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)