How Many Onto Functions Can Be Defined Between Sets of Different Sizes?

[kuahji]

# 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.

 

[VeeEight]

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)ⁿ \sum(-1)^k(n choose k) k^m

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