Relations & Functions
Onto Functions with Restrictions
Grade 12
Question:
<p>Let \(A = \{1, 2, 3, 4, 5\}\). The number of onto functions from A to A such that \(f(i) \neq i\) for all \(i\), is</p>
<p>(a) 44</p>
<p>(b) 120</p>
<p>(c) 56</p>
<p>(d) 76</p>
Step-by-Step Solution
Key Concept: This combines the concepts of surjective functions and derangements where no element maps to itself.
<p><strong>Solution:</strong> We need to count onto (surjective) functions from A to A where $f(i) \neq i$ for all $i$. This is the number of derangements of a permutation. Using the inclusion-exclusion principle with the constraint, the answer is 44.</p>
Correct Answer: A