(i) How many functions are there from $[\mathrm{m}] \rightarrow[\mathrm{n}]$?

(i) Suppose $\mathfrak{m} \leqslant n$. How many injections are there from $[m] \rightarrow[n]$?

(ii) Suppose $m \geqslant n$. How many surjections are there from $[m] \rightarrow[n]$?
For (i), there are clearly $n^{m}$ ( $n$ choices for each of the $m$ integers at the start)

For (ii), we have $n$ choices for the image of $1, n-1$ choices for the image of $2$, and so on until $m$ for which we have $n-m+1$ choices for its image. The answer is therefore

For (iii), we will use the principle of inclusion-exclusion and count the number of functions $[m] \rightarrow[n]$ that are not surjective. To this end, for $1 \leqslant i \leqslant n$, let $A_{i}$ be the set of functions $[\mathrm{m}] \rightarrow[\mathrm{n}]$ such that $i$ is not reached by the function. It is clear that for integers $1 \leqslant \mathfrak{i}_{1}<\cdots<\mathfrak{i}_{k} \leqslant n$, we have $\operatorname{Card}\left(A_{i_{1}} \cap \cdots A_{i_{k}}\right)=(n-k)^{m}$, because each element of [m] can be mapped to one of the $n-k$ integers of $[n]$ allowed. Thus, according to the principle of inclusion-exclusion, if we denote $s(m, n)$ as the number of surjections from $[m] \rightarrow[n]$, we have:

$$
\begin{aligned}
n!-s(m, n) & =\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)^{m} \\
& =\sum_{k=1}^{n}(-1)^{k+1}\binom{n}{k}(n-k)^{m}
\end{aligned}
$$

Thus,

$$
s(m, n)=\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(n-k)^{m}
$$

## 2) Proof of bijections in combinatorics

Definition 29. Let $E, F$ be two sets and $f: E \rightarrow F$ a function. We say that $f$ is bijective if it is both injective and surjective.

Proposition 30. Let $A$ and $B$ be two finite sets. Then $A$ and $B$ have the same cardinality if, and only if, there exists a bijection between $A$ and $B$.

Proof. Exercise.

In combinatorics, this proposition is often used in the following way. If we want to show that $a=b$, where $a, b \geqslant 0$ are integers, it suffices to find two finite sets $A$ and $B$ such that $\operatorname{Card}(A)=a$ and $\operatorname{Card}(B)=b$, and to construct a bijection between $A$ and $B$.

To verify that a function is bijective, it is sometimes convenient to exhibit the inverse function. More precisely:

Proposition 31. If $f: A \rightarrow B$ and $g: B \rightarrow A$ are two functions such that $f(g(b))=b$ for all $b \in B$ and $g(f(a))=a$ for all $a \in A$, then $f$ and $g$ are bijections (we say they are inverses of each other).

Proof. First, let's show that $f$ is surjective. Let $b \in B$. We know that $f(g(b))=b$, so $g(b)$ is a preimage of $b$, which means $f$ is surjective. To show injectivity, let $x, y \in E$ such that $f(x)=f(y)$ and show that $x=y$. We have $x=g(f(x))=g(f(y))=y$. The function $f$ is therefore injective, and since it is surjective, it is indeed bijective. By symmetry, $g$ is also bijective.