# Number of distinct surjective functions [duplicate]

Consider two sets A and B each with "n" elements. How many distinct surjective (onto) functions from A to B are possible?

• Isn't it $n!$, the number of all permutations of the set $\{1,2,\dots,n\}$? You need to cover every element of $B$ (there are $n$ of them), plus since $A$ has $n$ elements, only such functions are permutations. – TBTD Apr 25 '17 at 20:05

Note that a surjective function from $A$ to $B$, both having the same cardinality is an injection. (Hence, a bijection).

The first element of $A$ has $n$ options for B.

The second element of $A$ has $n-1$ options, avoiding the selected element, otherwise, it will not be a surjection.

The $i$-th element has $n-(i-1)$ options.

Multiplying them up, we have $n!$ such choices.

Alternatively,

you can also go through the first element of $B$ and let it choose its preimage. It has $n$ options.

Now choose the preimage for the second element of $B$, it can't choose the same element as the first as that would violate the definition of a function.

Repeat the argument and you will get $n!$.

• This relies on the alluded-to fact that injection = surjection for finite sets of the same cardinality; it might be good to state that explicitly. – Patrick Stevens Apr 25 '17 at 20:09
• I agree, thanks for the feedback. – Siong Thye Goh Apr 25 '17 at 20:10