Suppose $n$ objects are placed in a circular table in clockwise order. Find the no of permutations where $i$ cannot go to $i$ or $i+1$. i.e. $1$ cannot be mapped to $1$ or $2$, $2$ cannot be mapped to $2$ or $3$,... , $n$ cannot be mapped to $n$ or $1$.
Say the required no is $T(n)$.
What I did, first I fix $1 \in \{1,2,..,n\}.$ Now, $1$ can go to some $k \in \{3,4,..,n\}$ in $\binom{n-2}{1} = n-2$ ways.
Case 1. If $k\neq n$, then two subcases appear.
SubCase 1. $k \to 1$ and $1 \to k$. Rest can be arranged in $T(n-2)$ ways.
SubCase 2. $k \to$ some other element and from some other element comes back to $1$. We can consider 1 and k as same unit and can consider arrangement in $n-1$ elements in $T(n-1)$ ways.
Total count for case 1 is $(n-2)*\{T(n-2)+T(n-1)\}$.
Case 2. If $k = n$. This is the case where I stucked. Now how to proceed. Any help will be appreciated.
you may should try come to the problem from another angle: take the amount of all the permutations in a circle, which is $(n-1)!$, and decrease all the problematic permutations (every one's which mapping at least one element to itself) by using the "inclusion-exclusion principle".
for more info look at https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle