The following screenshot shows a lemma & proof from my combinatorics lecture notes
However, I am struggling to understand this result. Surely, since a surjective function is one for which every element in the range is mapped onto, every possible surjective function arises by choosing an element in the range and then choosing an element in the domain to be mapped on to it.
For example, if our domain is $$ A : = \{ a_1, \dots, a_n \} $$ and our range is $$ B := \{ b_1, \dots, b_k \} $$ then every surjective mapping arises by choosing, for each $b_i \in B$, some $a_j \in A$ such that $b_i = f(a_j)$. Clearly, since there are $n$ elements in our range, there are $n$ ways to choose such a value of $a_j$. Thus, since we must do this $k$ times, the total number of possibilities would be $n^k$ by the multiplication principle.
Clearly my reasoning is not correct, but I am unsure as to why. Can someone help me to understand the flaw in my logic?
There are two flaws in your logic. First is that, there may be more than one pre-image for a chosen $b_i$ from $B$. If there are $t$ pre-images of $b_i$ then this can be chosen from $A$ by ${n\choose t}$ ways, but you have taken $n={n\choose 1}$, that is, you have taken only one pre-image. But that's not sufficient(in case more than one pre-image) Second is that, If you take some particular preimage of $b_i$, from $A$, this can be done in ${n\choose 1}=n$ ways, but after choosing that , a second pre-image of a different $b_j$ can be chosen by ${n-1\choose 1}$ ways, and so on.(You have chosen all preimages in $n$ ways, which is not the case)
Now for the clarification of the given result, $S(n,k)$ is Stirling's number of second kind which is defined by "all possible ways to partition a $n$ element set in $k$ parts".Now for $|A|=n, |B|=k$ ,if $f:A\to B$ is a onto map then the preimage make $k$ partition of $A$. Now there are $S(n,k)$ $k$-partition of $A$ and for each partition, there are $k!$ surjective maps. So the, total number of surjective map is, $k!S(n,k)$.