number of functions with fixed point from finite set in itself

Question

For a given set $A$, with $|A|=n, \, n\in\mathbb{N}$, I want to know the cardinality of $$M:= \{f:A\rightarrow A| f \mbox{ has at least one fixed point}\}.$$

Does anyone know if this is possible and if yes has a source or a answere for me?

Answer 1

Let $X_i$ be the set of functions from $A$ to itself such that $i$ is a fixed point.

We try to count $\left|\bigcup\limits_{i=1}^n X_i\right|$

Clearly $|X_i| = n^{n-1}$ as each of the $n-1$ elements in the domain apart from $i$ have $n$ options for where they map to.

Similarly, $|X_i\cap X_j|$ with $i\neq j$ is of size $n^{n-2}$ as each of the $n-2$ elements apart from $i$ and $j$ have $n$ options each for where they map to.

Expanding the above via Inclusion-Exclusion, we arrive at a final count of:

$$\sum\limits_{i=1}^n(-1)^{i+1}\binom{n}{i}n^{n-i}$$

---

Alternatively, we can count the opposite event.

If no element were a fixed point, then each element has $n-1$ options. Subtracting this from the total:

$$n^n - (n-1)^n$$

which you can find is equal to the above.