K-перестановки

Назвемо перестановку чисел $1\dots n$ $k$-перестановкою, якщо будь-які два сусідні елементи в ній відрізняються не більше ніж на $k$.

Знайдіть кількість $k$-перестановок чисел $1\dots n$.