Permutations in an k-sorted array
Let $N(n,k)$ be the number of $k$-sorted arrays on $n$ elements. At each position we have at most $(2k+1)$ possible elements, giving an upper bound of $(2k+1)^n$. On the other hand, suppose that we divide $\{1,\ldots,n\}$ into $n/k$ blocks of size $k$ (assuming for simplicity that $k$ divides $n$), and apply an arbitrary permutation on each block. All of these arrays are $k$-sorted, showing that $N(n,k) \geq k!^{n/k}$. In total,
$$
k!^{n/k} \leq N(n,k) \leq (2k+1)^n \\
\frac{n}{k} (k \log k - k + O(\log k)) \leq \log N(n,k) \leq n \log(2k+1)
$$
We conclude that $\log N(n,k) = \Theta(n \log k)$.

For the exact expression, consult a paper of Kløve or the OEIS.