Help with surjective maps

1. Jun 17, 2011

battousai

1. The problem statement, all variables and given/known data

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

How many surjective maps are there from S to S?

2. Relevant equations

n/a

3. The attempt at a solution

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

2. Jun 17, 2011

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

3. Jun 17, 2011

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.

4. Jun 17, 2011

LCKurtz

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

5. Jun 17, 2011

battousai

Got it. Thanks.