There are $10$ students in a classroom, each one has a notebook. All notebooks are collected and then distribute them again but randomly. What is the probability that at least one student retrieves their own notebook?
My idea was to solve using the complement: "probability that none of them get back their own notebook". I'm trying to find a recurrence that count the number of functions from $A = \{1,2,3, ..., n\}$ to $A$, where the image is not equal to the pre-image. I created an algorithm that throws the following results for different values of $n$:
$n → result$
$0 → 0$
$1 → 0$
$2 → 1$
$3 → 2$
$4 → 9$
$5 → 44$
$6 → 265$
$7 → 1854$
$8 → 14833$
$9 → 133496$
$10 → 1,334,961$
So, the answer should be:
$1 - 1,334,961/10!$
$ = 0.632120535...$
for every $i=1,2,\cdots,10$, we have $$\mathbb{P}(A_i)=\frac{ 9!}{10!}$$ for every $1 \le i<j\le10$, we have $$\mathbb{P}(A_i\cap A_j)=\frac{ 8!}{10!}$$ for every $1 \le i<j< k\le 10 $, we have $$\mathbb{P}(A_i\cap A_j\cap A_k)=\frac{7!}{10!}$$ and so on. Therefore $$\mathbb{P}\left(\bigcup\nolimits_{i=1}^{10}{{A_i}}\right)=\sum_{i=1}^{10}\frac{(-1)^{i+1}\binom{10}{i}\times (10-i)!}{10!}$$ or $$\mathbb{P}\left(\bigcup\nolimits_{i=1}^{10}{{A_i}}\right)=\sum_{i=1}^{10}\frac{(-1)^{i+1}}{i!}$$