Help Me Find # of Onto Functions from B -> B

[James889]

Hi,

I have a simple question i'd like some help with

let B = \{1,2,3,4,5\}

How many functions from B -> B are onto ?

A kick in the right direction would be nice

 

[lanedance]

say you have a function defined on
f : a \in A \rightarrow f(a) = b \in B

A function is onto if for every b in B, there exists an a, such that f(a) = b

in this case A = B
f : b \in B \rightarrow f(b) = b' \in B
and there must be a b for every b'

so what else can you say about f?

 

[HallsofIvy]

There are, of course, 5⁵ functions from B to B.

In order to be onto, a function from two sets of the same size (which, of course, includes functions from one set to itself) must also be one-to-one. I think that makes the problem simpler.

Choose a number to map "1" to - you have 5 choices. Once that is done, you cannot map anything else to that so you now have 4 choices to map "2" to, 3 to map "3" to, etc. See the point?

 

[James889]

There are, of course, 5⁵ functions from B to B.

In order to be onto, a function from two sets of the same size (which, of course, includes functions from one set to itself) must also be one-to-one. I think that makes the problem simpler.

Choose a number to map "1" to - you have 5 choices. Once that is done, you cannot map anything else to that so you now have 4 choices to map "2" to, 3 to map "3" to, etc. See the point?

I see the point, so an element can map to itself?
So is the function also one-to-one ?