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!

Homework Help: Number of Onto Functions

  1. May 7, 2009 #1
    # of Onto Functions

    How many onto functions are there from a set with four elements to a set with two elements?

    My math professor gave an example of a set with 50 to a set with 35 (again asking for the number of onto functions). The way to go about the problem according to him is to just do 50*49*48*...*17*16 (basically the first element in the second set has 50 choices, the next 49, etc.). For the first two problems problems I had a set of 3 elements to a set of 2 elements, so using this reasoning (& it seemed to make sense), I'd do 3*2=6. It works. The next one I had was a set of 3 to a set of 3, so 3*2*1=6. It works. Then I get the one above, 4*3=12. It does not work. The answer should be 14. But without writing out all the possibilities, I'm trying to find a better way to understand these problems and be able to solve them more efficiently.
  2. jcsd
  3. May 7, 2009 #2
    Re: # of Onto Functions

    I have not done this type of stuff in years but I will help out since you are not getting any replies.

    Let S(m,n) denote the number of surjective (onto) functions from a set of m elements to a set of n elements.

    Then S(m,n) = (-1)n [tex]\sum[/tex](-1)k(n choose k) km

    where the sum runs from 1 to n and (n choose k) is the binomial coefficient (I couldn't find the symbol for it).

    This may also help: http://en.wikipedia.org/wiki/Bell_number
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook