Counting nearly-sorted permutations

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

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.