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: Understand the condition f(f(x)) = f(x)

This means that for every x ∈ S, f(x) is a fixed point of f. If we denote y = f(x), then f(y) = y. So every element in the image of f must be a fixed point.

Step 2: Characterize the structure

Let F = {a ∈ S : f(a) = a} be the set of fixed points. The image of f must be a subset of F, and moreover, the image must equal F (every fixed point must be in the image, otherwise we could remove it from consideration). So f maps S onto some non-empty subset F ⊆ S where f(a) = a for all a ∈ F.

Step 3: Count by cases based on fixed point sets

For S = {1, 2, 3}, we consider all non-empty subsets as potential fixed point sets:

Case 1: One fixed point

Choose 1 element to be fixed: C(3,1) = 3 ways. The other 2 elements must map to this fixed point: 1 way each. Total: 3 × 1 = 3 functions.

Case 2: Two fixed points

Choose 2 elements to be fixed: C(3,2) = 3 ways. The remaining 1 element can map to either fixed point: 2 ways. Total: 3 × 2 = 6 functions.

Case 3: Three fixed points

All three elements are fixed: C(3,3) = 1 way. Each maps to itself: 1 way. Total: 1 × 1 = 1 function.

Step 4: Sum all cases

Total number of functions = 3 + 6 + 1 = 10

Generalization for S = {1, 2, ..., n}:

For each non-empty subset F of size k (where 1 ≤ k ≤ n), there are k^(n-k) functions mapping the n-k non-fixed elements to F. Thus, the total count is: ∑(k=1 to n) C(n,k) × k^(n-k)

∴ Answer: B

Question:

Step-by-Step Solution

Master Sets, Relations & Functions with Mathbee