This is based on the question at here
I want to know how many onto functions are there from set $A={1,2,3,4,5}$ to set $B={a,b,c}$.
This is how I did it:
First i tried to find the functions which are not onto
case 1:
All in A maps to a single element of B
There are 3 ways for this
case2:
When mappings are made for only two elements in range.
First we have to select 2 out of 3 elements.That can be done in $3\choose 2$$=3$ways.
Consider mappings to only (a,b).
Number of ways when only one item maps to a=5
Number of ways when only two items maps to a=$5\choose 2$
Number of ways when only three items maps to a=$5\choose 3$
Number of ways when only four items maps to a=$5\choose 4$
Total mappings only to (a,b)=30.
Hence in case 2 total non onto mappings are$=30*3=90$
By case1 and case2 Total non onto mappings are $90+3=93$
Therefore onto mappings are $3^5=93=150$
My question is in the given answer mappings for case2 is obtained as , there are 2^5 = 32 possible functions, so we have 3*32 = 96 functions here that aren't onto
.
What's wrong with my method?
Can someone please tell me where I have done wrong?
Best Answer
$2^5$ also counts the maps with only one element in the image. When you then multiply by $3$ you double count the functions that send only to one element.
For example the function $f_a$ (that sends everything to $a$). Is counted in the case $(a,b)$ and $(a,c)$. Since there are $3$ such functions we have to subtract $3$ to the outcome and we get $96-3=93$ which you had before.