Permutations & Combinations
Derangements and counting functions
Grade 11
Question:
<p>Let <em>A</em> = {1, 2, 3, 4, 5, 6, 7}. The number of bijections <em>f</em> : <em>A</em> → <em>A</em> such that <em>f</em>(<em>i</em>) = <em>i</em> for at least 4 values of <em>i</em> is:</p>
<p>(a) 70</p>
<p>(b) 92</p>
<p>(c) 21</p>
<p>(d) 1</p>
Step-by-Step Solution
Key Concept: Count bijections where at least 4 fixed points exist by considering cases: exactly 4 fixed, exactly 5 fixed, exactly 6 fixed, and exactly 7 fixed points. Use derangements for non-fixed elements.
<p><strong>Step 1: Identify cases</strong></p><p>For at least 4 fixed points, count: exactly 4, 5, 6, or 7 fixed points.</p><p><strong>Step 2: Case 1 - Exactly 4 fixed points</strong></p><p>Choose 4 positions to fix: C(7,4) = 35</p><p>Remaining 3 elements must form a derangement: D₃ = 2</p><p>Contribution: 35 × 2 = 70</p><p><strong>Step 3: Case 2 - Exactly 5 fixed points</strong></p><p>Choose 5 positions to fix: C(7,5) = 21</p><p>Remaining 2 elements must form a derangement: D₂ = 1</p><p>Contribution: 21 × 1 = 21</p><p><strong>Step 4: Case 3 - Exactly 6 fixed points</strong></p><p>Choose 6 positions to fix: C(7,6) = 7</p><p>The 7th element must map to itself (forced): D₁ = 1</p><p>Contribution: 7 × 1 = 7</p><p><strong>Step 5: Case 4 - Exactly 7 fixed points</strong></p><p>Identity function: 1 way</p><p><strong>Step 6: Total</strong></p><p>70 + 21 + 7 + 1 = <strong>99</strong></p><p>∴ Answer: B</p>
Correct Answer: B