Question

The number of bijections \(f(\cdot)\) from the set \(S = \{1, 2, 3, 4\}\) to itself such that \(f(f(n)) = n\), for all \(n \in S\), is ________. (Answer in integer)

Hint:

f(f(n)) = n means f is an involution: count fixed points plus swapped pairs among 4 elements.

Answer 1

Correct Answer: 10

Step 1: Understand what the condition means.
A function f is a bijection from S to itself with f(f(n)) = n for every n in S. Applying f twice always brings you back to the start, so f must be its own inverse. A permutation with this property is called an involution. In an involution every element is either a fixed point, where f(n) = n, or part of a pair that swaps with each other, where f(a) = b and f(b) = a for a not equal to b. No cycle of length 3 or more is allowed, because a 3-cycle needs three applications of f to return to the starting element, not two.

Step 2: Split into cases by how many swapped pairs are used.
The set S has 4 elements. A swapped pair uses up exactly 2 elements, so the number of pairs used can be 0, 1, or 2 (using 3 pairs would need 6 elements).

Step 3: Count each case.
Case with 0 pairs: every element is fixed. This is just the identity function, so there is exactly 1 way.
Case with 1 pair: pick 2 of the 4 elements to swap, and leave the other 2 fixed. The number of ways to choose which 2 elements swap is \(\binom{4}{2} = 6\).
Case with 2 pairs: all 4 elements are split into two swapped pairs, with no element left fixed. The number of ways to split 4 labeled elements into 2 unordered pairs is 3, since for {1,2,3,4} the possible pairings are {1,2}{3,4}, {1,3}{2,4}, and {1,4}{2,3}.

Final Answer:
Add up the three cases: \(1 + 6 + 3 = 10\). \[ \boxed{10} \]