Find the number of onto functions from set A (4 elements) to set B (3 elements)

Question

Find the number of onto (surjective) functions from a set $A$ with 4 elements to a set $B$ with 3 elements.

(JEE Main 2022)

Solution — Step by Step

Total number of functions from $A$ to $B$ : each of the 4 elements in $A$ can map to any of the 3 elements in $B$ . So total $= 3^4 = 81$ .

An onto function must “hit” every element of $B$ . We need to subtract functions that miss at least one element of $B$ .

Let $A_i$ = set of functions that miss element $b_i$ from $B$ .

We want: $|A_1^c \cap A_2^c \cap A_3^c| =$ Total $- |A_1 \cup A_2 \cup A_3|$

By inclusion-exclusion:

|A_1 \cup A_2 \cup A_3| = \sum|A_i| - \sum|A_i \cap A_j| + |A_1 \cap A_2 \cap A_3|

$|A_i|$ = functions missing one specific element = $2^4 = 16$ . There are $\binom{3}{1} = 3$ such terms.

$|A_i \cap A_j|$ = functions missing two specific elements = $1^4 = 1$ . There are $\binom{3}{2} = 3$ such terms.

$|A_1 \cap A_2 \cap A_3|$ = functions missing all three elements = $0^4 = 0$ .

|A_1 \cup A_2 \cup A_3| = 3(16) - 3(1) + 0 = 48 - 3 = 45

\text{Onto functions} = 81 - 45 = \mathbf{36}

Why This Works

A function from $A$ to $B$ is onto if every element of $B$ is the image of at least one element of $A$ . Since $|A| = 4 > |B| = 3$ , onto functions exist (they wouldn’t if $|A| < |B|$ ).

The inclusion-exclusion principle handles the “at least one element missed” condition systematically. Directly counting onto functions is hard, but counting functions that miss specific elements is easy — if we exclude $k$ elements from $B$ , the remaining $(3-k)$ elements give $(3-k)^4$ functions.

Alternative Method — Using the formula directly

The number of onto functions from a set of $m$ elements to a set of $n$ elements ( $m \geq n$ ) is:

\sum_{k=0}^{n} (-1)^k \binom{n}{k} (n-k)^m

For $m = 4$ , $n = 3$ :

\binom{3}{0}(3)^4 - \binom{3}{1}(2)^4 + \binom{3}{2}(1)^4 - \binom{3}{3}(0)^4

= 81 - 48 + 3 - 0 = 36

This formula is worth memorising for JEE. For small values, you can also use: onto functions from $m$ to $n$ = $n! \times S(m, n)$ where $S(m, n)$ is the Stirling number of the second kind. For $S(4, 3)$ : partition 4 elements into 3 non-empty groups = 6 ways, then assign to 3 elements of $B$ = $6 \times 3! = 36$ .

Common Mistake

A frequent error is computing $3^4 - 3 \times 2^4 = 81 - 48 = 33$ and stopping there — forgetting the inclusion-exclusion correction for double-counting. When we subtract functions missing $b_1$ , missing $b_2$ , and missing $b_3$ , we over-subtract functions that miss TWO elements (they get subtracted twice). We must add those back. Always complete all terms of inclusion-exclusion.

Question

Solution — Step by Step

Why This Works

Alternative Method — Using the formula directly

Common Mistake

Try These Next