How many onto functions are there from a set with four elements to a set with two elements?
I thought of this question in such a way: Lets say set 1: {a,b,c,d}, set 2: {x,y} Method: 4C2 * 2 * 2 = 24 Logic: Out of the four elements, I choose 2 of them. (This 2 will each be attached to x and y respectively). The other 2 elements left in set 1 can then select to go to x or y. (2 choices each).
However the answer to solution is: $ \binom{4}{3}\binom{1}{1} + \binom{4}{2}\binom{2}{2} + \binom{4}{1}\binom{3}{3}$ = 14
I get the solution's logic but can someone help me point out from my logic which cases did I double counted? Appreciate it.
If you choose $a$ and $b$ to send to $x$ and $y$, and then $c$ and $d$ get sent there as well, that’s the same as if you chose $c$ and $d$ in the first place, and then $a$ and $b$ followed.
In this case, you could really write down all 24 of your list, and then just see which ones are redundant.
There are only $2^4=16$ total functions from $\{a,b,c,d\}\to\{x,y\}$, anyway, and only two of them fail to be onto. That’s probably the easiest way to count it.