How many onto (or surjective) functions are there from an \(n\)-element \((n…
2012
How many onto (or surjective) functions are there from an \(n\)-element \((n \geq 2)\) set to a 2-element set?
- A.
\(2^n\) - B.
\(2^n - 1\) - C.
\(2^n - 2\) - D.
\(2(2^n - 2)\)
Attempted by 221 students.
Show answer & explanation
Correct answer: C
Answer: 2^n - 2
Explanation:
Total functions: Each of the n elements in the domain can be sent to either of the two targets, so there are 2^n total functions.
Non-surjective functions: The only functions that are not onto are the two constant maps (one sending every element to the first target, the other sending every element to the second target).
Therefore onto functions = total functions − non-surjective functions = 2^n − 2.
Example: For n = 3 there are 2^3 − 2 = 6 onto functions; for n = 2 there are 2^2 − 2 = 2 onto functions.
A video solution is available for this question — log in and enroll to watch it.