permutation on a circle within some distance Assuming $n$ children sitting around a round table. For example, 7 children.
At the second time they changed seats, so this is a permutation $\omega$.
Each child's new seat and previous seat define a distance, if the permutation is $6 1 2 5 3 4 0$
, so now the child last round took seat #$0$ is now seating at #$6$, so he moved $1$ distance, or $d(0)=1$.
Call the biggest distance of all the children the distance of the circle permutation. For example the distance of all the children are $1,0,0,1,1,2,1$, so the $d(\omega) = \max_i d(i) = 2$.
Now the questions is, for $n$ children, if the distance shall be no more than $k$, how many permutations $N(n,k)$ are there?
Of course $\forall n$, $N(n,0)=1$, i.e. no one moves.
If $k=1$ it's also simple, $N(n,1) = F(n+1)+F(n-1)+2$, here $F(n)$ is the Fibonacci numbers starting with $F(0)=0$, and $F(1)=1$.
for example if $n=10$, then $N(10,1)=135$.
But when $k\ge 2$ it's turns quite complex I couldn't find a nice solution. For example by programming it shows $N(10,2) = 6208$ but I couldn't find a close form or recursive form for it.
Is there a way to compute it? Or, the simple case, is there a close or recursive form for $N(n,2)$?
 A: Let $a(n)= N(n, 2)$. The sequence $a(n)$ is available on the OEIS as A000804, which includes many references.
An interesting reference there is "Permutations with Restricted Displacement", in which they also look at these numbers as the number of permutations with restrictions. They do not look at permutations where elements can only move 2 in both directions, but they look at permutations where elements can move at most 4 to the right, which is the same number. (can you think of the bijection to prove that?)
In the notation of that paper, you are looking at $a(n, 5)$. $a(n, 4)$ is the last one for which they provide the recurrence relation, as that is the last simple one. For $a(n, 5), a(n, 6), a(n, 7), a(n, 8)$ and $a(n, 9)$ they refer to this paper. For each $k$ you are looking for $N(n, k) = a(n, 2k+1)$.
The recursive formula for $N(n, 2) = a(n, 5) = a(n)$ presented there (formula 1.3) can be written as
$$
\begin{aligned}
a(n) &= 2a(n-1) + 2a(n-2)-2a(n-4)\\
&-8a(n-5) -6a(n-6)- 2a(n-7)\\
&+ 2a(n-9) + a(n-10) + 24
\end{aligned}
$$
This recursion relation is valid for $n \geq 15$. For $n \leq 5$, we simply have $a(n) = n!$. This leaves the values for $n = 6, \cdots, 14$ to be precomputed (or you can find them here).
This python snippet uses that recursion to compute the first 100 values of $a(n)$ instantly.
The recursions for $N(n, 3) = a(n, 7)$ and $N(n, 4) = a(n, 9)$ are also available there but the formulas get huge. Precomputed values are also available on the OEIS under A008305.
