Question 50

We need the number of onto functions from set $X$ ($|X| = 4$) to set $Y$ ($|Y| = 3$).

By the Principle of Inclusion-Exclusion, the number of onto functions is given by:

where $m = 4$ and $n = 3$.

Calculating each term:

• $k = 0$: $\binom{3}{0} 3^4 = 1 \times 81 = 81$
• $k = 1$: $-\binom{3}{1} 2^4 = -3 \times 16 = -48$
• $k = 2$: $+\binom{3}{2} 1^4 = +3 \times 1 = +3$
• $k = 3$: $-\binom{3}{3} 0^4 = 0$

Total number of onto functions:

Alternatively, partitioning 4 distinct elements into 3 non-empty subsets must be of sizes $2 + 1 + 1$. The number of ways to partition is $\binom{4}{2} = 6$, and the number of ways to assign the 3 subsets to the 3 target elements is $3! = 6$. Total onto functions = $6 \times 6 = 36$.