K-permutation

Let's call a permutation of $n$ numbers $1\dots n$ a $k$-permutation if any two adjacent elements in it differ by no more than $k$.

Find the number of $k$-permutations of the numbers $1\dots n$.