Counting Surjective Maps from a Finite Set to Itself

[battousai]

Homework Statement

Let S = {1,2,3,...,n}

How many surjective maps are there from S to S?

Homework Equations

n/a

The Attempt at a Solution

The book's answer is n!

However, I thought that total number of surjective maps = n^n because 1-1 isn't required. Where am I wrong?

 

[hunt_mat]

This is understandable as a surjective map from itself to itself, and this is essential just the set S being rearranged, so the answer will be n!.

Mat

 

[Arianwen]

1-1 is implicitly required, because each element of the domain can only map to one element of the range - so to map to every element of the range you'll need a 1-1 mapping.

 

[LCKurtz]

Homework Statement

Let S = {1,2,3,...,n}

How many surjective maps are there from S to S?The book's answer is n!

However, I thought that total number of surjective maps = n^n because 1-1 isn't required. Where am I wrong?

But since S is finite, if the map wasn't 1-1 it couldn't be onto, could it?

 

[battousai]

1-1 is implicitly required, because each element of the domain can only map to one element of the range - so to map to every element of the range you'll need a 1-1 mapping.

But since S is finite, if the map wasn't 1-1 it couldn't be onto, could it?

Got it. Thanks.