Let $A, B$ be two finite sets with $|A| = n$ and $|B| = k$. How many injective mappings $f : A \rightarrow B$ are there? Furthermore, show that the number of surjective mappings $f: A \rightarrow B$ equals $k!S_{n,k}$.
I guess this has to do with Stirling numbers and something with the following identity $x^n = \sum^{n}_{k=0}S_{n,k}(x)_k$, but I don't know how can I proceed or let alone count this kind of functions. How can I solve this problem?
Best Answer
As shown in Counting surjective functions, the number of surjections $A \stackrel{onto}\longrightarrow B$, with $\lvert A\rvert = n, \lvert B\rvert = k$, is: $$ \sum_{j=0}^{k}(-1)^{k-j}\binom{k}{j}j^n = k!\, S_{n,k} \tag{# of surjections $n\to k$} $$ See that answer for why this is so.
Counting injections $A\stackrel{1-1}\longrightarrow B$ is simpler. Assume $A=\{1,\dotsc,n\}, B=\{1,\dotsc, k\}$. Each subset $Y\subseteq B$ of size $n$ corresponds to $n!$ many injections: there's the canonical order-preserving bijection $A\stackrel{\sim}\to Y$, and then $n!$ many others which arise from permuting the elements of $A$ (or, equivalently, the elements of $Y$). Moreover, every injection arises in this way. So the number of injections $A\stackrel{1-1}\longrightarrow B$ is: $$ n! \binom k n = \frac {k!} {(k-n)!} $$