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