Permutations & Combinations
Functions - Onto Functions
Grade 11
Question:
<p>Given that \(A = \{x_1, x_2, x_3, \ldots, x_7\}\); \(B = \{y_1, y_2, y_3\}\). 3 elements in \(A\) having image \(y_2\) can be chosen in \(^7C_3\) ways. Now we are left with 4 elements in \(A\) which are to be associated with \(y_1\) or \(y_3\), that is, each of 4 elements \(A\) has 2 choices \(y_1\) or \(y_3\), that is, in \((2)^4\) ways. But there are 2 ways when one element of \(B\) will remain associated. The required number of onto functions from \(A\) to \(B\) such that exactly 3 elements of \(A\) map to \(y_2\) is:</p>
<p>(1) \(^7C_3 \cdot 2^4\)</p>
<p>(2) \(^7C_3 \cdot (2^4 - 1)\)</p>
<p>(3) \(^7C_3 \cdot (2^4 + 2)\)</p>
<p>(4) \(14 \cdot ^7C_3\)</p>
Step-by-Step Solution
Key Concept: An onto function requires every element of B to have at least one preimage. After fixing 3 elements mapping to y₂, the remaining 4 elements must map to y₁ and y₃ such that both receive at least one element (to avoid leaving y₁ or y₃ unmapped).
<p><strong>Step 1:</strong> Choose 3 elements from 7 to map to y₂: <sup>7</sup>C₃ ways</p><p><strong>Step 2:</strong> Remaining 4 elements can map to {y₁, y₃}: 2⁴ = 16 ways (each element has 2 choices)</p><p><strong>Step 3:</strong> For the function to be onto, we must exclude cases where all 4 elements map only to y₁ (1 way) or only to y₃ (1 way)</p><p><strong>Step 4:</strong> Valid mappings of 4 elements to {y₁, y₃} = 2⁴ - 2 = 16 - 2 = 14</p><p><strong>Step 5:</strong> Total onto functions = <sup>7</sup>C₃ × 14 = 35 × 14 = <strong>490</strong></p><p>∴ Answer: D</p>
Correct Answer: D