How to show that the displaying numbers of a onto function is k!S(n,k)?

Question

Let it be $A$,$B$ sets that $|A|$=$n$, $|B|$=$k$ and $|A|>|B|$.

How to show that the displaying numbers of an onto function $f$:$A$ $\rightarrow$ $B$ is:

$\begin{Bmatrix} n \\ k\end{Bmatrix}$$k!$

Answer 1

Well, $\left\lbrace \begin{array}{c} n \\ k \end{array}\right\rbrace$ counts the number of ways to partition a set of $n$ elements into $k$ non-empty partitions. We can induce a partition from an onto function $f : A \rightarrow B$, by looking at the inverse image of elements of $B$. Specifically, if $B = \lbrace y_1, \ldots, y_k \rbrace$, then the partition of $A$ is given by: $$\lbrace f^{-1} \lbrace y_1 \rbrace, \ldots f^{-1} \lbrace y_k \rbrace \rbrace,$$ where $f^{-1} \lbrace y_m \rbrace = \lbrace x \in A : f(x) = y_m \rbrace$, if you haven't seen that notation before.

However, we cannot associate each partition with a unique $f$, because the partition does not retain information about which part maps to which element of $B$. But, for each of these partitions of $A$ into $k$ sets, we have $k!$ ways of mapping the parts in the partition to elements of $B$. Therefore, the total number of onto functions is $\left\lbrace \begin{array}{c} n \\ k \end{array}\right\rbrace k!$, as stated.