GATE CS 2015 Set 2 Q40 — Sets, Relations and Functions

We need to find the number of onto (surjective) functions from a set $X$ of size $n = 4$ to a set $Y$ of size $m = 3$.

We can solve this using two standard methods:

Method 1: Principle of Inclusion-Exclusion (PIE)

The total number of onto functions from a set of size $n$ to a set of size $m$ is given by the formula:

Substituting $n = 4$ and $m = 3$:

Method 2: Partitioning (Stirling Numbers of the Second Kind)

An onto function maps $4$ elements of $X$ to $3$ elements of $Y$ such that no element in $Y$ is left empty. This is equivalent to partitioning the $4$ elements of $X$ into $3$ non-empty subsets, and then assigning each subset to a unique element in $Y$.

1. The only way to partition $4$ elements into $3$ non-empty groups is of the size distribution $\{2, 1, 1\}$.
2. The number of ways to partition $4$ distinct elements into $3$ unlabeled groups of sizes $2, 1, 1$ is given by the Stirling number of the second kind, $S(4, 3)$: $$S(4, 3) = \frac{4!}{2! \cdot 1! \cdot 1! \cdot 2!} = 6$$
3. Since the target set $Y$ has labeled elements, we can assign these $3$ groups to the $3$ elements of $Y$ in $3!$ ways: $$\text{Total onto functions} = S(4, 3) \times 3! = 6 \times 6 = 36$$

Thus, the number of onto functions is 36.