Derangement problem but with functions instead of permutations, using inclusion-exclusion.

Question

How many functions $f : [n] \to [n]$ are there with no fixed points, i.e. such that $f(i) \ne i$ for all $i$? Use inclusion-exclusion to solve it.

Answer 1

For $k\in[n]$ let $A_k$ be the set of functions from $[n]$ to $[n]$ that have $k$ as a fixed point. Then the principle of inclusion-exclusion says that

$$\begin{align*} \left|\bigcup_{k\in[n]}A_k\right|&=\sum_{\varnothing\ne I\subseteq[n]}(-1)^{|I|+1}\left|\bigcap_{k\in I}A_k\right|\\ &=\sum_{k=1}^n(-1)^{k+1}\binom{n}kn^{n-k}\,: \end{align*}$$

there are $\binom{n}k$ subsets $I\subseteq[n]$ such that $|I|=k$, and there are $n^{n-k}$ functions from $[n]\setminus I$ to $[n]$ whose set of fixed points includes all of $I$. There are $n^n$ functions from $[n]$ to $[n]$, so there are

$$\begin{align*} n^n-\sum_{k=1}^n(-1)^{k+1}\binom{n}kn^{n-k}&=n^n+\sum_{k=1}^n(-1)^k\binom{n}kn^{n-k}\\ &=\sum_{k=0}^n(-1)^k\binom{n}kn^{n-k} \end{align*}$$

functions from $[n]$ to $[n]$ with no fixed points.

As a sanity check let $n=3$. If we list $f(1),f(2)$ and $f(3)$ in that order, the $8$ functions from $[3]$ to $[3]$ with no fixed points can be described by the triples $231$, $312$, $211$, $311$, $212$, $232$, $331$, and $332$, and indeed

$$\sum_{k=0}^3(-1)^k\binom3k3^{3-k}=27-27+9-1=8\,.$$

Answer 2

For each $i$ there are exactly $n - 1$ non-fixed point values for $f(i)$, so $(n -1)^n$ functions in all.