Permutations & Combinations
Functions and surjections
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). Count fixed points carefully: if at least 4 elements are fixed, we need exactly 4, 5, 6, or 7 fixed points, and the remaining elements must form a derangement or permutation that maintains surjectivity.
<p><strong>Step 1: Recognize the constraint.</strong> For f: A → A to be surjective with |A| = 7, f must be a bijection (permutation). The condition f(i) = i for at least 4 values means at least 4 fixed points.</p><p><strong>Step 2: Count by number of fixed points.</strong> We need exactly k fixed points where k ∈ {4, 5, 6, 7}.</p><p><strong>Step 3: Case k=7 (all fixed).</strong> Only identity function: 1 way.</p><p><strong>Step 4: Case k=6 (exactly 6 fixed).</strong> Choose 6 to fix: C(7,6) = 7. The remaining 1 element must map to itself (forced), giving 1 way. Total: 7 ways.</p><p><strong>Step 5: Case k=5 (exactly 5 fixed).</strong> Choose 5 to fix: C(7,5) = 21. The remaining 2 must form a derangement. D(2) = 1 (only transposition: swap them). Total: 21 × 1 = 21 ways.</p><p><strong>Step 6: Case k=4 (exactly 4 fixed).</strong> Choose 4 to fix: C(7,4) = 35. The remaining 3 must form a derangement. D(3) = 2 (either (1 2 3) or (1 3 2) in cycle notation). Total: 35 × 2 = 70 ways.</p><p><strong>Step 7: Sum all cases.</strong> 1 + 7 + 21 + 70 = <strong>99</strong></p><p>∴ Answer: D</p>
Correct Answer: D