1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Is this correct? Functions!

  1. Nov 6, 2006 #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!
     
  2. jcsd
  3. Nov 6, 2006 #2

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  4. Nov 6, 2006 #3

    arildno

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    Dearly Missed

    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.
     
  5. Nov 6, 2006 #4

    arildno

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    Dearly Missed

    As for the second one, try to interpret the multiplication: 4*2+3*2=14
     
  6. Nov 6, 2006 #5
    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:
    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!
     
  7. Nov 6, 2006 #6

    0rthodontist

    User Avatar
    Science Advisor

    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
     
  8. Nov 7, 2006 #7

    arildno

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    Dearly Missed

    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.
     
  9. Nov 7, 2006 #8
    Thanks for the help guys!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?