Rearrangement of $13$ people passing books to each other where no one passes books to same person EDIT: I still don't understand the answer Math Lover already gave. I'd like an answer that explicitly builds on my attempt/thoughts and goes step by step in detail, hence bountying my question.
Actual Question
Here's yet another problem from my probability textbook:

A reading society of $13$ members passes books in circular rotation from member to member in defined order. If for a new year the order be rearranged at random, what is the chance that no one will pass his books to the same member as in the previous years?

Here's what I did. Without loss of generality let's say the initial passing order of members is from $x_1$ to $x_2$ to $x_3$ etc. all the way up to $x_{13}$ to $x_1$. Let's first calculate the denominator. We start with $x_1$, and then we have $12$ choices for the next member, then $11$, all the way down to $1$, so the denominator either $12!$ or $12! - 1$, depending on whether or not we include the initial arrangement in what the problem statement calls "the order be rearranged at random".
Let's next calculate the numerator. We start with $x_1$, and then we have $11$ choices for the next member since we can't use $x_2$, and then we have $10$ choices for the next member since we can't use the member that was ahead of that member in the initial configuration, all the way down to $1$, so the numerator is $11!$.
Therefore the desired probability is either ${1\over{12}}$ or ${{11!}\over{12! - 1}}$.
However, this is certainly not correct since we're undercounting i.e. consider a rearrangement that begins with $x_1x_3x_2$. Then there were $11$ choices for the second slot, $10$ choices for the third slot. But then there's $10$ choices again for the fourth slot because $x_3$ is before $x_2$ in the passing order. So what do I need to add to the probability I calculated to account for this phenomenon?
 A: You will have to apply Principle of Inclusion Exclusion.
There are $12! ~ $ circular permutations without restriction.
Now if one of them is passing book to the same person, that gives us $11!$ ways of passing books and there are $13$ ways to choose the person. So we subtract $13 \cdot 11!$.
If two of them are passing book to the same persons, we have $10!$ permutations and $ \displaystyle {13 \choose 2}$ ways of choosing those two people.
So applying Principle of Inclusion-Exclusion, number of desired permutations are
$\displaystyle \left[\sum_{i=0}^{12} (-1)^i{13 \choose i} (12-i)! \right] - 1$
The last $(-1)$ is to subtract the permutation where all of them are passing book to the same next person as current.
Dividing it by $12!$ will give the desired probability.
Also see, https://oeis.org/A000757
A: Basically same as @Math Lover's answer.
Total number of ways: $12!$
To that we must substract the prohibited arrangements.
The pair $x_1, x_2$, for example, is prohibited, because the $x_1$ element is "wrong", it has on its side the same element as in the original. There $11!$ arrangements (circular permutations) that include that case. Because the posible wrong elements are 13, we must multiply that count by $13$, or $\binom{13}{1}$.
But we are overcounting: to the above we must substract the arrangements with two or more "wrong elements. Fixing any two "wrong" elements, we have $10!$ arrangements that include them. Which we must multiply by $\binom{13}{2}$.
And so on.. This is the inclusion-exclusion principle at work.
Then the total count of allowed arrangements is
$$ 12! - \binom{13}{1} 11 ! + \binom{13}{2} 10 ! + \cdots  $$
A: One simple way of seeing this is realizing that we can use the multiplicative principle for this problem.
For simplicity we can label our books to track them, it wouldn't change anything if we do, nether by the way we do it, by owner, title or more simple letters , they would be name A to M, in some order the only thing important is that the names don't change.
Now we can translate the problem to counting all the arrangements that satisfy that after exchanging the book everyone end up with a different letter (that meaning they get a different book). we can write $A\rightarrow B$ for the person that had A give her book to B,an example of a possible configuration is:
$$A\rightarrow B\\
B\rightarrow C\\
C\rightarrow D\\
D\rightarrow E\\
E\rightarrow F\\
F\rightarrow G\\
G\rightarrow H\\
H\rightarrow I\\
I\rightarrow J\\
J\rightarrow K\\
K\rightarrow L\\
L\rightarrow M\\
M\rightarrow A
$$
And this one will represent that they will pass the book to the person with the next letter in the alphabet (and M to A since M is the last book), but it is only one possible way, and we need to find every possible one.
We can notice that A can pass the book to any one but herself, then she has 12 option, the person that received the book from A can do the same but there is a catch this person can't pass her book to the same person than A so he will have one option less than A, this can be done for every letter, the next one will have 10 options and so on, until the person that will only have one choice to give it to the last person who doesn't have a book. finally for knowing the total amount of  combination we will use the multiplicative principle, that say that if you have a number of ways of doing each step, the number of ways of doing the hole process is the multiplication of the ways of each step so we will have:
$$A\rightarrow 12\rightarrow 11\rightarrow 10\rightarrow 9\rightarrow 8\rightarrow 7\rightarrow 6\rightarrow 5\rightarrow 4\rightarrow 3\rightarrow 2\rightarrow 1
$$
so we will have $1\cdot 2\cdot 3 \cdots 12=12!$
note: It can happen that for example $E\rightarrow F\rightarrow A\rightarrow E$ and we will be unable to continue our process because E already give her book but in this case (of being a loop before giving all the books) we can choose some one that haven't give his book and continue the process without a problem (since this person will have the same amount of options as the people without new book yet)
hope this is helpful :)
