Counting Onto Functions with Different Sets

[mr_coffee]

Hello everyone.

The question is:
How many onto functions are there from a set with four elements to a set with threee elements?

If i let x = {a,b,c,d,}
y = {x,y,z}

Step 1: construct an onto function from {a,b,c} to {x,y,z}
step 2:
choose whether to send d to x or to y or to z. I directly found there are 9 ways to perorm step 1, and 3 ways to perform step 2. Thus by the multiplication rule (9)(2) = 18 ways to define functions in the first category. But the book did a similar example and then ended up adding an additional 2 to their answer after doing the multiplication rule. So would it be 18 + 2 = 20?

The question in the book was the following:
How many onto functions are there from a set with 4 elements to a set with 2 elements?
they got an answer of 14 orginally 12 then added 2 more at the end for some reason.
THanks!

 

[AKG]

You can't just add 2 for no reason. Unless you know why the book did it, why would you do it? Also, there's a problem with your answer, because you are only counting the functions where d maps to the same thing that something else maps to. Of course, there will alyaws be 2, and only 2, elements of x which map to the same thing, but d doesn't always have to be one of those element.

 

[arildno]

It is better, I think, to first determine the number of distinct 2-subsets that must map to the same element. This is seen to be 3+2+1=6 subsets.
Now, for each such subset there will exist 3*2*1=6 onto functions, since the subset itself may map onto 3 different numbers, and so on.
Thus, there should exist 6*6=36 such onto functions in total.

 

[arildno]

As for the second one, try to interpret the multiplication: 4*2+3*2=14

 

[mr_coffee]

thanks for the responces guys, arildno, im' going to try to see if I understand exactly what you ment to fully get the problem... when you said:

It is better, I think, to first determine the number of distinct 2-subsets that must map to the same element. This is seen to be 3+2+1=6 subsets.

Are you saying break the domain down into the following subsets:
x = {a,b,c,d,}
y = {x,y,z}

x = { {a,b},{b,c},{c,d},{a,d},{b,d}, {c,a} }
I think I got al the possible combinations, but what made you choose groups of 2?
Also can you tell me your thought process when you borke it down into 3 + 2 + 1 = 6, rather than writing out all the possible combinations like i did?

Thanks again!

 

[0rthodontist]

Your book probably does it with inclusion and exclusion. First you count how many functions in total there are (3^4). Then you subtract the number of functions that do not map to each of the 3 elements (2^4 * 3). But this subtracts too much, so you add the number of functions that do not map to two of the 3 elements (1^4 * 3) and then this might have added too much so you subtract the number of functions that do not map to any of the 3 elements (0). So the answer is 3^4 - 3 * 2^4 + 3 = 36

 

[arildno]

I chose groups of two, since necessarily, two elements will map to the same element in the value domain.
Each such two-group defines a set of functions distinct from the other two-group's sets of functions.
As for 3+2+1=6,
note that a will be present in 3 groups, b will be in two groups not including a, and c and d may form a two-group as well.

 

[mr_coffee]

Thanks for the help guys!