math-combo-01

# Counting Idempotent Self-Maps

Let $A = \{1, 2, 3, 4, 5\}$. Count the number of functions $f : A \to A$ that satisfy
$$f(f(x)) = f(x) \qquad \text{for every } x \in A.$$

(Such a function acts as the identity on its own range.)

Give your answer as a single integer.

To find the number of functions $f : A \to A$ such that $f(f(x)) = f(x)$ for all $x \in A$, where $A = \{1, 2, 3, 4, 5\}$, we analyze the properties of such functions.

A function satisfying $f(f(x)) = f(x)$ is called an idempotent function.
Let $R = \text{Im}(f) = \{f(x) \mid x \in A\}$ be the image of $f$.
For any $y \in R$, there exists some $x \in A$ such that $y = f(x)$. Applying $f$ to both sides, we get $f(y) = f(f(x))$. By the idempotent property, $f(f(x)) = f(x) = y$. Thus, $f(y) = y$ for all $y \in R$.
This means that $f$ acts as the identity function on its image $R$.
Conversely, if $f$ acts as the identity on its image $R$, then for any $x \in A$, $f(x) \in R$, so $f(f(x)) = f(x)$.

To count the number of such functions, we can sum over the possible sizes of the image $R$. Let $k = |R|$. Since $A$ has 5 elements, $k$ can range from 1 to 5.
For a fixed size $k$:
1.  We choose the subset $R \subseteq A$ of size $k$. The number of ways to do this is $\binom{5}{k}$.
2.  Once $R$ is chosen, the values of $f$ on $R$ are fixed: $f(y) = y$ for all $y \in R$.
3.  For the remaining $5 - k$ elements in $A \setminus R$, each element must map to some element in $R$ (since $R$ is the image). There are $k$ choices for each of these elements. Thus, there are $k^{5-k}$ ways to define $f$ on $A \setminus R$.

So, the number of idempotent functions with image size $k$ is $\binom{5}{k} k^{5-k}$.
We sum this quantity for $k = 1, 2, 3, 4, 5$:

-   For $k = 1$: $\binom{5}{1} \cdot 1^{5-1} = 5 \cdot 1^4 = 5 \cdot 1 = 5$.
-   For $k = 2$: $\binom{5}{2} \cdot 2^{5-2} = 10 \cdot 2^3 = 10 \cdot 8 = 80$.
-   For $k = 3$: $\binom{5}{3} \cdot 3^{5-3} = 10 \cdot 3^2 = 10 \cdot 9 = 90$.
-   For $k = 4$: $\binom{5}{4} \cdot 4^{5-4} = 5 \cdot 4^1 = 5 \cdot 4 = 20$.
-   For $k = 5$: $\binom{5}{5} \cdot 5^{5-5} = 1 \cdot 5^0 = 1 \cdot 1 = 1$.

Total number of functions = $5 + 80 + 90 + 20 + 1$.
Summing these up:
$5 + 80 = 85$
$85 + 90 = 175$
$175 + 20 = 195$
$195 + 1 = 196$

Thus, there are 196 such functions.

\boxed{196}