-1
$\begingroup$

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

| cite | improve this question | | | | |
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – TBTD Apr 25 '17 at 20:05
1
$\begingroup$

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!$.

| cite | improve this answer | | | | |
$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Patrick Stevens Apr 25 '17 at 20:09
  • $\begingroup$ I agree, thanks for the feedback. $\endgroup$ – Siong Thye Goh Apr 25 '17 at 20:10

Not the answer you're looking for? Browse other questions tagged or ask your own question.