3
$\begingroup$

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)

$\endgroup$
9
$\begingroup$

Your problem is solved in the paper Spheres of Permutations under the Infinity Norm — 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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – al92 Oct 28 '14 at 4:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.