Let $\mathrm{n}$ interns at the Montpellier internship go swimming and leave their Animath t-shirts scattered on the sand. They return and take a $\mathrm{t}$-shirt completely at random. What is the probability that no one ends up with their own t-shirt?
Each intern is assigned a different number between 1 and $n$, and we denote $x_{i}$ as the number of the student taking the $i$-th t-shirt. Thus, $\left(x_{1}, \ldots, x_{n}\right)$ is a permutation of $(1, \ldots, n)$. Let's calculate the probability that at least one person retrieves their t-shirt using the principle of inclusion-exclusion. For $1 \leqslant i \leqslant n$, let $A_{i}$ be the set of permutations such that $x_{i}=i$. It is clear that for $1 \leqslant \mathfrak{i}_{1}<\cdots<\mathfrak{i}_{k} \leqslant n$, we have:

$$
\operatorname{Card}\left(A_{i_{1}} \cup \cdots \cup A_{i_{k}}\right)=(n-k)!
$$

Thus, according to the inclusion-exclusion principle:

$$
\begin{aligned}
\operatorname{Card}\left(A_{1} \cup A_{2} \cup \cdots \cup A_{n}\right) & =\sum_{k=1}^{n}(-1)^{k+1} \sum_{1 \leqslant i_{1}<\cdots<i_{k} \leqslant n} \operatorname{Card}\left(A_{i_{1}} \cup \cdots \cup A_{i_{k}}\right) \\
& =\sum_{k=1}^{n}(-1)^{k+1} \sum_{1 \leqslant i_{1}<\cdots<i_{k} \leqslant n}(n-k)! \\
& =\sum_{k=1}^{n}(-1)^{k+1}\binom{n}{k}(n-k)! \\
& =\sum_{k=1}^{n}(-1)^{k+1} \frac{n!}{k!} .
\end{aligned}
$$

The desired probability is $1-\operatorname{Card}\left(A_{1} \cup A_{2} \cup \cdots \cup A_{n}\right) / n!$, which is:

$$
\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}+\cdots+(-1)^{n} \frac{1}{n!}
$$

## - Injections, Surjections, Bijections -

## 1) Injections and Surjections

Definition 27. Let $E, F$ be two sets and $f: E \rightarrow F$ be a function.

(i) We say that $f$ is injective if for all $x, y \in E$ with $x \neq y$, $f(x) \neq f(y)$.

(ii) We say that $f$ is surjective if for all $y \in F$, there exists $x \in E$ such that $f(x)=y$.

We say that $E$ is the domain, $F$ is the codomain. If $f(x)=y$, we say that $x$ is the preimage of $y$ and $y$ is the image of $x$.

To show that $f: E \rightarrow F$ is injective, we often show that if $x, y \in E$ are such that $f(x)=f(y)$, then $x=y$ (see the course on functional equations).

We introduce the notation $[\mathfrak{n}]=\{1,2, \ldots, n\}$ for an integer $n \geqslant 1$.

Proposition 28. There exists an injection $[\mathrm{m}] \rightarrow[\mathrm{n}]$ if and only if $m \leqslant n$. There exists a surjection $[m] \rightarrow[n]$ if and only if $m \geqslant n$.

Proof. Exercise.

In practice, we use the previous proposition in combinatorics as follows: to show that $a \leqslant b$, we construct two sets $A, B$ such that $\operatorname{Card}(A)=a, \operatorname{Card}(B)=b$, and an injection from $A$ to $B$. Or, to show that $a \geqslant b$, we construct two sets $A, B$ such that $\operatorname{Card}(A)=a, \operatorname{Card}(B)=b$, and a surjection from $A$ to $B$.