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.

We are given a finite set $ A = \{1, 2, 3, 4, 5\} $, and we want to count the number of **idempotent functions** $ f : A \to A $ satisfying:

$$
f(f(x)) = f(x) \quad \text{for all } x \in A.
$$

Such functions are called **idempotent self-maps**.

---

### Key Insight:

A function $ f $ satisfies $ f(f(x)) = f(x) $ for all $ x $ **iff** $ f $ is the identity on its image (range). That is, if we let $ B = \operatorname{im}(f) \subseteq A $, then:

- For every $ y \in B $, $ f(y) = y $,
- For every $ x \in A $, $ f(x) \in B $.

So to construct such a function:

1. Choose a subset $ B \subseteq A $ to be the image of $ f $. Let $ |B| = k $, where $ k = 0, 1, 2, 3, 4, 5 $. But note: can $ k = 0 $? No — because a function from a nonempty set to itself must have nonempty image. So $ k \ge 1 $.

2. For each $ b \in B $, we must have $ f(b) = b $ (since $ f $ acts as identity on its image).

3. For each $ x \in A \setminus B $, we can assign $ f(x) $ to be **any** element of $ B $.

So for a fixed subset $ B $ of size $ k $:

- There are $ k^{n - k} $ ways to define $ f $ on the $ n - k $ elements outside $ B $, where $ n = |A| = 5 $.

- The number of such subsets $ B \subseteq A $ of size $ k $ is $ \binom{5}{k} $.

Therefore, total number of idempotent functions is:

$$
\sum_{k=1}^{5} \binom{5}{k} \cdot k^{5 - k}
$$

Let’s compute term by term:

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

Add them up:

$$
5 + 80 + 90 + 20 + 1 = 196
$$

---

### Final Answer:

$$
\boxed{196}
$$