• Support PF! Buy your school textbooks, materials and every day products Here!

Number of Onto Functions

  • Thread starter kuahji
  • Start date
  • #1
394
2
# 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.
 

Answers and Replies

  • #2
614
0


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
 

Related Threads for: Number of Onto Functions

  • Last Post
Replies
10
Views
4K
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
8
Views
3K
  • Last Post
Replies
1
Views
906
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
1
Views
681
  • Last Post
Replies
6
Views
2K
Replies
2
Views
979
Top