Permutations & Combinations
Functions - surjective/bijective counting
Grade 11
Question:
<p>Let \(A = \{1, 2, 3, 4, 5, 6, 7\}\). The number of surjective functions defined from \(A\) to \(A\) such that \(f(i) = i\) for at least four values of \(i\) from \(i = 1, 2, \ldots, 7\) is:</p>
<p>7!</p>
<p>92</p>
<p>126</p>
<p>407</p>
Step-by-Step Solution
Key Concept: A surjective function from a finite set to itself with the same cardinality must be a bijection (permutation). If f(i)=i for at least 4 values, we need exactly 4, 5, 6, or 7 fixed points and ensure the remaining elements form valid bijections.
<p><strong>Key Insight:</strong> A surjective function f: A → A where |A|=7 must be a bijection (permutation).</p><p><strong>Step 1:</strong> Identify cases by number of fixed points k ≥ 4.</p><p><strong>Step 2 (k=7):</strong> All elements fixed: f(i)=i for all i. Count = C(7,7)×0! = 1</p><p><strong>Step 3 (k=6):</strong> Choose 6 fixed points: C(7,6)=7 ways. The remaining 1 element must map to itself (forced). Count = 7×1 = 7</p><p><strong>Step 4 (k=5):</strong> Choose 5 fixed points: C(7,5)=21 ways. The remaining 2 elements must form a derangement (swap): D₂=1. Count = 21×1 = 21</p><p><strong>Step 5 (k=4):</strong> Choose 4 fixed points: C(7,4)=35 ways. The remaining 3 elements must form a derangement: D₃=2 (either (234) or (243) cycles). Count = 35×2 = 70</p><p><strong>Step 6:</strong> Total = 1 + 7 + 21 + 70 = <strong>99</strong></p><p>∴ Answer: D</p>
Correct Answer: D