Is this correct? Functions!

  • Thread starter mr_coffee
  • Start date
  • #1
1,629
1
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 simlar 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!
 

Answers and Replies

  • #2
AKG
Science Advisor
Homework Helper
2,565
4
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.
 
  • #3
arildno
Science Advisor
Homework Helper
Gold Member
Dearly Missed
9,970
132
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.
 
  • #4
arildno
Science Advisor
Homework Helper
Gold Member
Dearly Missed
9,970
132
As for the second one, try to interpret the multiplication: 4*2+3*2=14
 
  • #5
1,629
1
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!
 
  • #6
0rthodontist
Science Advisor
1,230
0
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
 
  • #7
arildno
Science Advisor
Homework Helper
Gold Member
Dearly Missed
9,970
132
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.
 
  • #8
1,629
1
Thanks for the help guys!
 

Related Threads on Is this correct? Functions!

Replies
5
Views
4K
Replies
8
Views
738
  • Last Post
Replies
7
Views
706
  • Last Post
Replies
3
Views
874
  • Last Post
Replies
10
Views
1K
  • Last Post
Replies
7
Views
1K
Replies
5
Views
1K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
2
Views
994
Top