Contar permutaciones casi ordenadas

Question

Dejemos que $[n]$ denota el conjunto $\{1,2,\ldots,n\}$ .

Llamamos a una permutación $\sigma:[n]\to[n]$ , $(n,k$ )-casi ordenados si $$\forall i\in [n]: |\sigma(i) - i|\le k,$$

es decir, cada elemento se desplaza como máximo $k$ lugares en comparación con la permutación de identidad.

Cuántos $(n,k)$ -¿existen permutaciones casi ordenadas?

---

Por ejemplo, 5 $(4,1)$ -existen permutaciones casi ordenadas:

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

---

Para $(4,2)$ tenemos $14$ permutaciones: $$(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)$$

Answer 1

El número de $(n,k)$ -permutaciones casi ordenadas está dada por la permanente de la $n\times n$ Matriz de Toeplitz $M$ para lo cual $M_{ij}$ es igual a uno si $|i-j|\leq k$ y cero en caso contrario. Mira este También la página de Wikipedia.

Answer 2

Estos números aparecen en la OEIS como A130152 . No hay ninguna indicación de una fórmula para estos números en forma cerrada.