Thread: Onto Function Problems

Hi again guys,

The following two problems is from an onto section of my discrete math textbook. I don't understand what they are asking for. I asked a tutor for help, and he didn't know how to do it either.. Please help! .. Got finals today..

How many onto functions are there from a set with three elements to a set with five elements?

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

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

Originally Posted by aeubz

Hi again guys,

The following two problems is from an onto section of my discrete math textbook. I don't understand what they are asking for. I asked a tutor for help, and he didn't know how to do it either.. Please help! .. Got finals today..

1)How many onto functions are there from a set with three elements to a set with five elements?

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

3)How many onto functions are there from a set with four elements to a set with three elements?

Do you know what it means to be onto? It means everything in the second set is in the image of the first set.

1) a function sends something in the domain to something in the range. It can only send it to 1 thing though, otherwise it is not a function. So is there anyway 3 elements could possibly hit all 5 elements of the range codomain? no. So there are 0 functions that can do this

I will do one more, and leave the last one up to you.

2) we may as well just number the elements say in A the domain let the set be {1,2,3,4} and the range B={0,1}

I will use a bit of bad notation to describe these functions to save time. The coordinates (a,b,c,d) will represent a is where 1 is sent, b is where 2 is sent, c is where 3 is sent d is where 4 is sent.

All possible functions are
(0,0,0,0)
(0,0,0,1)
(0,0,1,0)
(0,0,1,1)
(0,1,0,0)
(0,1,0,1)
(0,1,1,0)
(0,1,1,1)
(1,0,0,0)
(1,0,0,1)
(1,0,1,0)
(1,0,1,1)
(1,1,0,0)
(1,1,0,1)
(1,1,1,0)
(1,1,1,1)

The ones in red are the ones that are not onto because they do not hit everything in the codomain B. Understand? So how many of those are actually onto?

Think you can handle 3)? I do. Good luck on the exam.

#1) No onto functions.(Permutation is a negative)

#2) Ahh, so it seems like a permutation. So 4 P 2 = 4!/(4-2)! = 12, however, it seems you need to add by 2 to get a total of 14. Why is this?

#3) If the permutations is correct. It seems 4!/(4-3)! = 24 + 3?? = 27.??

BTW, Thank you!

Sorry - getting confused about where the borders lie between group theory and combinatorics...so just ignore this post, if you will...

Originally Posted by aeubz

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

The number of onto functions from a of N elements to a set of K elements is