Permutations & Combinations
Functions and Involutions
Grade 11
Question:
<p>Let <em>A</em> = {1, 2, 3, 4, 5}. Find the total number of functions <em>f</em> : <em>A</em> → <em>A</em> such that <em>f</em>(<em>f</em>(<em>x</em>)) = <em>x</em> for all <em>x</em> ∈ <em>A</em> (i.e., involutions on <em>A</em>). The answer is 26.</p>
Step-by-Step Solution
Key Concept: An involution f must satisfy f(f(x)) = x, meaning f is its own inverse. This forces elements into three categories: fixed points (f(x)=x) or 2-cycles (f(x)=y and f(y)=x). Count all valid partitions of A into fixed points and transpositions.
<p><strong>Step 1: Understand involution structure</strong><br/>If f(f(x))=x, then f must partition A into fixed points and 2-cycles (transpositions). No element can be in a longer cycle.</p><p><strong>Step 2: Count by number of 2-cycles</strong></p><p><strong>Case 1 (0 pairs):</strong> All 5 elements fixed. Involutions = 1</p><p><strong>Case 2 (1 pair):</strong> Choose 2 elements to swap: C(5,2) = 10 involutions</p><p><strong>Case 3 (2 pairs):</strong> Choose 4 elements, partition into 2 pairs: C(5,4)×[C(4,2)/2!] = 5×3 = 15 involutions</p><p><strong>Case 4 (≥3 pairs):</strong> Impossible (would need ≥6 elements)</p><p><strong>Step 3: Add all cases</strong><br/>Total = 1 + 10 + 15 = 26<br/>∴ Answer: <strong>26</strong></p>
Correct Answer: 26