The number of onto functions (surjective functions) from set 𝑋 = {1, 2, 3, 4}…
2015
The number of onto functions (surjective functions) from set 𝑋 = {1, 2, 3, 4} to set 𝑌 = {𝑎, 𝑏, 𝑐} is __________.
Answer: 36 — Key idea: count all functions and remove those that miss at least one value (inclusion–exclusion). Total functions from X to Y: 3^4 = 81. Functions that miss…
Attempted by 219 students.
Show answer & explanation
Correct answer: 36
Key idea: count all functions and remove those that miss at least one value (inclusion–exclusion).
Total functions from X to Y: 3^4 = 81.
Functions that miss a particular element of Y: 2^4 = 16. There are C(3,1)=3 choices of which element is missed, so subtract 3×16 = 48.
Functions that miss two particular elements of Y: 1^4 = 1. There are C(3,2)=3 such pairs, so add back 3×1 = 3.
By inclusion–exclusion: 81 − 48 + 3 = 36. Hence there are 36 onto functions.
Alternative (brief): Stirling number S(4,3)=6 counts partitions of X into 3 nonempty preimage sets; assign these to the 3 elements of Y in 3! ways, giving 6×6=36.
A video solution is available for this question — log in and enroll to watch it.