Number of onto functions, why does my solution not work?

Question

I have a set $A$ with $4$ elements and a set $B$ with $3$ elements. We need to find all onto functions from $A$ to $B$.

My line of thought:

• Map each element in $A$ to $B$, where only one element in $A$ must be mapped to the same element in $B$.
• So for the first element in $A$, we have $3$ choices.
• For the second element in $A$, we have $2$ choices.
• For the third element in $A$, we have $1$ choice.
• Now map the fourth element in $A$ to any of the elements in $B$, hence $3$ choices. Total would be $3 * 2 * 1 * 3 = 18$.

This is wrong however, the solution is $36$.

The solution also uses a different approach. They say a pair of elements needs to map to the same element. Choose this pair in ${4\choose 2}=6$ ways. Then select any of the $3$ elements from $B$ as a mapping target. Then there are $2$ choices left, hence total is $6 * 3 * 2 = 36$

I find my approach more intuitive, however I wonder what I counted wrong. Seems I'm missing half of the possible solutions.

Answer 1

There is no reason why only one element of $A$ must be mapped to a given element of $B$. Let $A=\{a_1,a_2,a_3,a_4\}$ and $B=\{b_1,b_2,b_3\}$. Suppose $f(a_1)=f(a_2)=b_1, f(a_3)=b_2$ and $f(a_4)=b_3$. This is an onto function but you are not counting this function.

Answer 2

By your counting, the first two elements of $A$ cannot map to the same element of $B$.

Arguing along the lines you are using: The first element of $B$ comes from any of the four elements of $A$, the second from any of the remaining three, the third from any of the remaining two. The remaining element of $A$ can be mapped to any element of $B$, say $a_1 \mapsto b$ and $a_2 \mapsto b$, but we have overcounted. Both choosing $a_1 \mapsto b$ during the first three steps and $a_2 \mapsto b$ during the last step and choosing $a_2 \mapsto b$ during the first three steps and $a_1 \mapsto b$ during the last step produce the same map, so we have only $$ 4 \cdot 3 \cdot 2 \cdot 3 \cdot \frac{1}{2} = 36 $$ distinct maps.