1. Limited time only! Sign up for a free 30min personal 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!

Number of onto functions from 2 sets

  1. Feb 28, 2014 #1
    1. The problem statement, all variables and given/known data
    I have 2 sets, one with 5 elements (A) and the other two(B).
    How many onto functions can be made from A to B?

    2. Relevant equations



    3. The attempt at a solution
    My first thought is that it should be something like ##\frac{5!}{2!}=60##. I don't know if this is correct or not, I began counting them up manually but quickly found that it was not really feasible to do without mistakes. I've never been very good at these combinations problems and I can't say I ever really understand them.

    Thanks for the help.
     
  2. jcsd
  3. Mar 1, 2014 #2
    All the functions must have 5 inputs, and each input can give 2 things.
    So for each input there is 2 options.
    I would say that is 2^5 = 32 options.
     
  4. Mar 1, 2014 #3

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    That may count some functions twice.


    I would suggest looking at an easier case - - or easier cases.

    How about if set A contains i element and set B contains 2 elements?

    How about if set A contains 2 elements and set B contains 2 elements?

    How about if set A contains 3 elements and set B contains 2 elements?

    etc.
     
  5. Mar 1, 2014 #4

    pasmith

    User Avatar
    Homework Helper

    For convenience, let [itex]B = \{0,1\}[/itex]. Every function [itex]f : A \to B[/itex] can be written as
    [tex]
    f : a \mapsto \begin{cases} 0, & a \in C, \\
    1, & a \in A \setminus C,
    \end{cases}
    [/tex]
    for some [itex]C \subseteq A[/itex], and distinct functions result from distinct choices of [itex]C[/itex]. Thus there are exactly as many functions from [itex]A[/itex] to [itex]B[/itex] as there are subsets of [itex]A[/itex].

    You are asked for onto functions, which means that there must be at least one [itex]a \in A[/itex] such that [itex]f(a) = 0[/itex] and at least one [itex]b \in A[/itex] such that [itex]f(b) = 1[/itex]. Thus [itex]C[/itex] can be any subset of [itex]A[/itex] except the empty set and [itex]A[/itex] itself.
     
    Last edited: Mar 1, 2014
  6. Mar 1, 2014 #5

    pasmith

    User Avatar
    Homework Helper

    Actually it counts each function exactly once.

    Two functions [itex]f: A \to B[/itex] and [itex]g: A \to B[/itex] are equal if and only if [itex]f(a) = g(a)[/itex] for all [itex]a \in A[/itex]. Thus if you make a different choice for the image of some [itex]a \in A[/itex] you have a different function. Since there are [itex]\#B[/itex] choices for each [itex]f(a)[/itex] and the choices are independent, there are (assuming both sets are finite) [itex](\#B)^{(\#A)}[/itex] distinct functions, although not all of them are onto, which is what the question asks for.
     
  7. Mar 1, 2014 #6
    I think I understand. I don't recall ever being in class that discussed how these combinations are found mathematically, they always have assumed that a)I've already been taught or b)It is so straight forward that teaching it is a waste of time. Neither is true for me.

    Does anyone know of a website that explains this in great detail (except wikipedia because they lack multiple examples and is hard to read)?
     
  8. Mar 1, 2014 #7
    I don't get anywhere doing this really. For 2 there are two possibilities, for 3 there are 6 (I think) but for 4 there are too many for me to do by hand really. I'm at 11 now but there could be more that I'm not seeing. It gets to be too many options to keep track of for me.
     
  9. Mar 1, 2014 #8
    I found this link on math.stackexchange but the solution looks about 10x harder than would be expected for the freshman class I'm in...

    I also ended up getting 14 functions that were onto for 4->2.

    It seems that for my problem, though, I could do it like

    ##2^5-2(2-1)^5## which would be 30. The possible combinations minus the combinations that don't include the elements from B. This also works with all the other cases.

    Have I got the idea now?
     
  10. Mar 1, 2014 #9

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Here's another way to look at it: imagine that B is the set {0, 1}. Then every function from A to B is effectively a 5-digit binary number. So, there are 32 = 2^5.

    But, if the function is onto, then you cannot have 00000 or 11111. So, that leaves 30.

    So, you can now extend your counting of functions to larger sets.
     
  11. Mar 1, 2014 #10
    This helped me so much to understand right here. Thank you so much.
     
  12. Apr 16, 2015 #11
    if the 2nd set hs 2 elements, the no of onto fns would be 2^n - 2 where n is the no of elements in the 1st set....so 4 ur qn it would be 32-2=30...this works only in cases where d 2nd set has 2 elements though....
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted