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.
Best Answer
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.