<p>Your problem is solved in the paper <a href="http://www.ii.uib.no/publikasjoner/texrap/pdf/2008-376.pdf">Spheres of Permutations under the
Infinity Norm &mdash; Permutations with limited displacement</a> by Torleiv Kløve.</p>

<p>See also <a href="https://oeis.org/A002524">A002524</a> 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.</p>

CC BY-SA 3.0
2014-10-28T04:11:30.660Z
Excellent, thanks! I've been messing with this for the last few days and haven't been making great progress. I wasn't aware of OEIS, so that's good to know.
al92
CC BY-SA 3.0
2014-10-28T03:41:41.310Z
2014-10-28T03:41:41.310Z
Yuval Filmus
<p>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$.</p>

<p>Define a sequence to be locally sorted with degree $k$ if $\forall s_i \in S |p(i) - i | \leq k$. </p>

<p>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".</p>

<p>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.</p>

<p>For handiness, here's some Python code to use when checking results:</p>

<p><code>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)
</code></p>

<ds.algorithms><sorting><dynamic-programming>
Locally sorted sequences
al92
# Locally sorted sequences

(Asked by: username_0 on 2014-10-28)

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

**Tags:** ds.algorithms, sorting, dynamic-programming

---

## 1 answers

### Answer by username_1 on 2014-10-28. Score: 9 | Accepted answer

Your problem is solved in the paper [Spheres of Permutations under the
Infinity Norm — Permutations with limited displacement](http://www.ii.uib.no/publikasjoner/texrap/pdf/2008-376.pdf) by Torleiv Kløve.

See also [A002524](https://oeis.org/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.

> **Comments:**
> **username_0**: Excellent, thanks! I've been messing with this for the last few days and haven't been making great progress. I wasn't aware of OEIS, so that's good to know.  

---

