Sets, Relations & Functions Question - None

Question

$ S = \{1, 2, 3\} $, $ f : S \to S $ satisfies the property: $ \forall x \in S,\, f(f(x)) = f(x) $. How many different functions are there for $ f(x) $?
[Note: Can you generalize the result for $ S = \{1, 2, 3, \ldots, n\} $?]

Accepted Answer

Step 1: Interpret the condition. f(f(x)) = f(x) means f(x) is always a fixed point. So if y is in the range of f, then f(y) = y.

Step 2: Structure of f. Choose a non-empty subset R ⊆ S to be the range. On R, we must have f(x) = x (identity). For elements not in R, each must map to some element in R.

Step 3: Count for S = {1,2,3}. For each non-empty R ⊆ S:

• |R| = 1: Choose 1 element for R (3 ways), f is determined. Each of 3 elements maps to this 1 fixed point = 3 functions

• |R| = 2: Choose 2 elements for R (3 ways), f is identity on R. Each of 1 remaining element maps to one of 2 elements in R = 3 × 2¹ = 6 functions

• |R| = 3: R = S (1 way), f is identity on all of S = 1 function

Step 4: Total count. 3 + 6 + 1 = 10 functions

Generalization: For S = {1,2,...,n}, the answer is: $$\sum_{k=1}^{n} \binom{n}{k} k^{n-k}$$

This equals the sum over all non-empty subsets of size k of (ways to choose k fixed points) × (ways to map remaining n−k elements to those k points).

∴ Answer: B (10)

Question:

Step-by-Step Solution

Master Sets, Relations & Functions with Mathbee