In how many ways can they rearrange such that each person is in a new seat and no 2 persons swap? Beforehand, each person is assigned a seat (n seats). How many ways can they rearrange such that each person is in a new seat and no 2 people swap?
I'm guessing $(n-1)!$, but I have no idea on how to get the answer.
I was trying to get the answer to this problem:
A small class of nine boys are to change their seating arrangement by drawing their new
seat numbers from a box. After the seat change, what is the probability that there is only
one pair of boys who have switched seats with each other and only three boys who have
unchanged seats?
where I got:
$(9C3 * 6C2 *4!)/9!$ but I realized that none of the (4!) people should be on the same seat. And no pair of students swapped seats
The answer to this problem is $9C3*6C2*3!/9!$. I want to find a generalization, with n seats, how many ways can you arrange n people such that no 2 people swap and no one is in the same seat.
 A: I think there is a way to write a recurrence relation by the following reasoning: we are counting the permutations of $\left\{1 , \ldots  , n\right\}$ which decomposition in cycles contains only cycles having at least $3$ elements. Let ${X}_{n}$ be that number. We can start with ${X}_{1} = {X}_{2} = 0$ and ${X}_{3} = 2$. Conventionally, we take ${X}_{0} = 1$.
Let $n  \geqslant  3$. We choose $k  \geqslant  2$ elements in $\left\{1 , \ldots  , n-1\right\}$ to form a cycle with the element $n$. There are $\binom{n-1}{k}$ ways to find these elements and there are $k !$ ways to align them in a row to build the cycle with element $n$. For the remaining $n-k-1$ elements, we choose one of the
${X}_{n-k-1}$ valid permutations. Hence we obtain the relation
\begin{equation}
{X}_{n} = \sum _{k = 2}^{n-1} \binom{n-1}{k} \  k ! \  {X}_{n-k-1}
= (n-1)!\sum _{k = 2}^{n-1} \frac{{X}_{n-k-1}}{(n-k-1)!}
\end{equation}
This easily entails the relation $X_n = (n-1)X_{n-1} + (n-1)(n-2) X_{n-3}$.
Note that this order 3 relation can be shown directly by another way of counting the permutations:
Second reasoning We can separate the valid permutations between the permutations for which the number $n$ belongs to a 3-cycle (there are $(n-1)(n-2) X_{n-3}$ of them because there are $(n-1)(n-2)/2$ ways of choosing the two other elements of the 3-cycle and each choice gives two possible cycles) and the permutations for which the number $n$ belongs to a larger cycle. Those are obtained by inserting the number $n$ in one of the cycles of a valid permutation of the $n-1$ first elements. For a given such permutation, there are exactly $n-1$ places where to insert the $n$-th element, between one of the $n-1$ first numbers and its successor in a cycle. Hence there are $(n-1)X_{n-1}$ such permutations. This proves the order 3 relation.
Clearly, the same reasoning shows that if we generalize and we count instead the number $Y_n$ of permutations of $\{1,\cdots, n\}$ where all the cycles have a length $\ge p$, then we have the relation
\begin{equation}
Y_n = (n-1) Y_{n-1} + (n-1)\cdots (n-p+1) Y_{n-p}
\end{equation}
