2
$\begingroup$

Let $[n]$ denote the set $\{1,2,\ldots,n\}$.

We call a permutation $\sigma:[n]\to[n]$, $(n,k$)-nearly sorted if $$\forall i\in [n]: |\sigma(i) - i|\le k,$$

i.e., every element is shifted at most $k$ places compared to the identity permutation.

How many $(n,k)$-nearly sorted permutations exist?


For example, 5 $(4,1)$-nearly sorted permutations exist:

  • (1,2,3,4)
  • (2,1,3,4)
  • (1,2,4,3)
  • (2,1,4,3)
  • (1,3,2,4)

For $(4,2)$, we have $14$ permutations: $$(1,2,3,4), (1,2,4,3), (1,3,2,4), (1,3,4,2), (1,4,2,3), (1,4,3,2), (2,1,3,4),$$ $$(2,1,4,3), (2,3,1,4), (2,4,1,3), (3,1,2,4), (3,1,4,2), (3,2,1,4), (3,4,1,2)$$

$\endgroup$
0
$\begingroup$

The number of $(n,k)$-nearly sorted permutations is given by the permanent of the $n\times n$ Toeplitz matrix $M$ for which $M_{ij}$ equals one if $|i-j|\leq k$ and zero otherwise. Look at this Wikipedia page, too.

$\endgroup$
0
$\begingroup$

These numbers appear in OEIS as A130152. There's no indication of a formula for these numbers in closed form.

$\endgroup$

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.