<p>Let <i>f</i> : <i>A</i> → <i>A</i> be an invertible function where <i>A</i> = {1, 2, 3, 4, 5, 6}. Then find the number of these functions in which at least three elements have self-image.</p>
Step-by-Step Solution
Key Concept: Use complementary counting: find total invertible functions (which are bijections = 6!) minus those with fewer than 3 fixed points. A fixed point occurs when f(x) = x. For bijections, use the inclusion-exclusion principle on derangements.
<p><strong>Step 1:</strong> Since f: A → A is invertible, f must be a bijection (permutation of A). We need at least 3 elements where f(x) = x (fixed points).</p><p><strong>Step 2:</strong> Use complementary counting. Total bijections = 6! = 720. Subtract those with 0, 1, or 2 fixed points.</p><p><strong>Step 3:</strong> For exactly k fixed points: choose k elements to fix, then count derangements of remaining (6-k) elements.</p><p><strong>Step 4:</strong> Derangement formula: D(n) = n!∑((-1)^i/i!) for i=0 to n</p><p>• D(0) = 1, D(1) = 0, D(2) = 1, D(3) = 2, D(4) = 9, D(5) = 44, D(6) = 265</p><p><strong>Step 5:</strong> Count with 0 fixed points: C(6,0)·D(6) = 1·265 = 265</p><p>Count with exactly 1 fixed: C(6,1)·D(5) = 6·44 = 264</p><p>Count with exactly 2 fixed: C(6,2)·D(4) = 15·9 = 135</p><p><strong>Step 6:</strong> Functions with fewer than 3 fixed points = 265 + 264 + 135 = 664</p><p><strong>Step 7:</strong> Functions with at least 3 fixed points = 720 - 664 = 56</p><p>∴ Answer: <strong>56</strong></p>
Correct Answer: 56