The number of onto functions (surjective functions) from set 𝑋 = {1, 2, 3, 4}…

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.