Q20
Consider two sets A = {2, 3, 5, 7, 11, 13} and B = {1, 8, 27}. Let f be a function from A to B such that for every element b in B, there is at least one element a in A such that f(a) = b. Then, the total number of such function f is
Answer: B
Asked: the number of functions from A (6 elements) onto B (3 elements), i.e. every element of B is hit.
Key idea: inclusion–exclusion. Count all functions, then remove those that miss one or more elements of B.
All functions: \(3^6=729\).
Functions missing a particular element of B: \(2^6=64\); 3 choices, so subtract \(3\times64=192\).
Functions missing two particular elements (everything maps to one element): \(1^6=1\); 3 choices, added back: \(+3\).
Onto functions \(=729-192+3=540\).
Answer: 540