Assume n people are sitting around a circular table. In how many ways we can re-arrange them so each person has a different person on his right? So I have this question.
n dancers are dancing in a circle, and then spread out and dance solo.
Now they come back together for another circular dance but now each dancer can't be standing in a way that he'll have the same person on his right from the previous circle.
How many options for the second circle are there?
*the order of the dancers in the first circle is given, the questions is only about the order in the second circle.
 A: For $n\geq3$ one obtains the numbers
$$1, 1, 8, 36, 229, 1625, 13208, \ldots\ .$$
I found them by counting admissible permutations, using a computer. I then looked this sequence up at OEIS, and it turned out to be sequence A000757,   where a reference is made to your problem. See there for more information.
A: This is a typical problem for applying inclusion exclusion principle. There are altogether $(n-1)!$ ways to arrange the dancers in a circle. From this number we should subtract the number of permutations with any two dancers being in the same order as in the previous circle. To perform this consider the dancer pair as a unit, which can be permuted with single dancers to obtain the number $\binom n1 (n-2)!$. However in doing this we heavily over-count because we multiply subtract the combinations with two (or more) pairs. To correct this we should now add combinations with two pairs fixed in the same order as in the previous circle. Here however we encounter a problem that the two pairs can be either separated (as 1-2,4-5) or joined (as 1-2-3). Fortunately this does not alter the count. Indeed in the first case we have two units (pairs) and $n-4$ single dancers.  In the second case we have one joined unit (triple) and $n-3$ single dancers. In both cases we have $2+(n-4)=1+(n-3)=n-2$ units to permute. One can show that the same is true for higher number of fixed pairs as well so that the final result is:
$$
\sum_{k=0}^{n-1}(-1)^k\binom nk (n-k-1)!+(-1)^n.
$$
The last term is singled out because direct application of the general expression for $k=n$ would involve the non-existing number $(-1)!$ as a factor. But clearly if we fix all $n$ pairs we obtain the initial circle as a single possible "permutation" which corresponds to the factor $1$.
