Number of functions $f : A \to A$ such that $f(f(x))=f(x)$

Solution 1:

This property is in general called idempotence. The linked page gives an argument for counting the number of idempotent functions $f:\{1,\dots,n\}\to \{1,\dots,n\}$, which I'll copy below:

A unary operation $f: \{1,\dots,n\}\to \{1,\dots,n\}$ is idempotent if it maps each element of $\{1,\dots,n\}$ to a fixed point of $f$. We can partition a set with $n$ elements into $k$ chosen fixed points and $n-k$ non-fixed points, and then $k^{n-k}$ is the number of different idempotent functions. Hence, taking into account all possible partitions, $$\sum _{k=0}^{n}{n \choose k}k^{n-k}$$

In particular, for $n = 5$, we get $196$. This compares to the total number of functions $f:\{1,\dots,5\}\to\{1,\dots,5\}$, which is $|\{1,\dots,5\}|^{|\{1,\dots,5\}|} = 3125$

Solution 2:

There are other possibilities. Here is one:

1 goes to 2

2 goes to 2

3 goes to 5

4 goes to 5

5 goes to 5

Expanding on this answer: The framework for these functions is to have some number (at least one) of fixed points, and have everything else map into the set of fixed points.

Solution 3:

Let $B_f = \{x\in A:f(x)=x\}$ and $C_f= \{x\in A: f(x)\ne x\}.$

For every $x\in C,$ the equality $f(f(x)) = f(x)$ implies that $f(x)\in B.$

Thus we can choose a function satisfying $f(f(x))=f(x)$ by

• choosing a set $\varnothing\ne B \subseteq A,$ and then
• choosing a function $f$ from $C=A\smallsetminus B$ into $B.$

The number of ways to choose a nonempty subset of $A$ is $2^{|A|}-1 = 2^5-1 = 31.$ The number of ways to choose a subset of any particular size $k\in\{1,\ldots,n\} = \{1,\ldots,5\}$ is $\dbinom n k = \dbinom 5 k.$

The number of ways to choose a function from $C$ into $B$ is $|B|^{|C|} = |B|^{|A|-|B|} = |B|^{5-|B|}.$

So the number you seek is $$ \sum_{k=1}^n \binom n k k^{5-k} = \sum_{k=1}^5 \binom 5 k k^{5-k} = 5 + 80 + 90 + 20 + 1. $$