I would like you to help me to prove two proofs correlated with Stirling numbers (the first one includes Stirling numbers of the second kind and the second one I guess Stirling numbers of the second kind as well-but I am not so sure about that).
The proofs are the below:
Let A,B be sets with $|A|=n$, $|B|=k$ and $|A|>|B|$.
- Prove that the number of functions $f : A \rightarrow B$ which are surjective (onto functions) equals to: $k!\cdot S(n, k)$. (This Stirling number is of the second kind)
- Find the number of functions $f : A \rightarrow B$ με $|f(A)|=m$, where $m \leq k$. (Ok, I know this question is not a proof but a problem...:D)
I am looking forward you to giving your answers.
I have to say thank you in advance!
Remember the definition of $S(n,k)$, the Stirling numbers of the second kind:
$S(n,k)$ is the number of partitions of $[n]$ into $k$ nonempty parts.
So, for the first question notice that for every function $f:[n] \rightarrow [k]$, the set $\{f^{-1}(1), f^{-1}(2), \cdots ,f^{-1}(n)\}$ is a partition of the set $[n]$ into $k$ nonempty subsets.
You can also think $k! \cdot S(n,k)$ as the number of ways we can put $n$ different balls into $k$ different boxes. First, we can partition $[n]$ into $k$ non-distinguishable parts in $S(n,k)$ ways, then we can label the $k$ parts with labels $1,2, \cdots ,k$ in $k!$ different ways.
The second question is just an application of the first. Regard the function $f: A \rightarrow B$ as a surjective function $f:A \rightarrow f(A)$ and use the above formula.