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 count the number of idempotent functions \( f: A \to A \) where \( A = \{1, 2, 3, 4, 5\} \) and \( f(f(x)) = f(x) \) for all \( x \in A \), we consider the image set \( B \) of \( f \). Each element in \( B \) must be a fixed point, and the function \( f \) maps elements not in \( B \) to elements in \( B \).

For each possible size \( k \) of \( B \) (from 1 to 5), the number of such functions is given by:
- \( \binom{5}{k} \) ways to choose \( B \),
- \( k^{5 - k} \) ways to define \( f \) on \( A \setminus B \).

Summing over all \( k \):
- \( k=1 \): \( 5 \times 1^4 = 5 \)
- \( k=2 \): \( 10 \times 2^3 = 80 \)
- \( k=3 \): \( 10 \times 3^2 = 90 \)
- \( k=4 \): \( 5 \times 4^1 = 20 \)
- \( k=5 \): \( 1 \times 5^0 = 1 \)

Adding these gives \( 5 + 80 + 90 + 20 + 1 = 196 \).

\boxed{196}