How to relate the number of all applications $X\to Y$ with the Stirling numbers of the second kind?

Question

I am studying Stirling numbers of the second kind, and I have just saw why $S(n,k)=\frac{1}{k!}\sum_{j=0}^{k-1}(-1)^{j}{k\choose j}(k-j)^{n}$ (knowing that $\sum_{j=0}^{k-1}(-1)^{j}{k\choose j}(k-j)^{n}$ counts the number of surjective functions from $X=\{x_{1},...,x_{n}\}$ into $Y=\{y_{1},...,y_{k}\}$). Now, in my notes appears that we can relate this Stirling numbers of second kind with the number of all applications $X\to Y$, naming $j$ the cardinal of the image, by this formula: \begin{equation*} k^{n}=\sum_{j=1}^{k}{k\choose j}j!S(n,j) \end{equation*} And I am having some trouble in visualizing it. My first approach was trying to manipulate the first relation with the surjective ones, but i got stucked. Then I have thought about trying to read what the right side means: If $j=1$, we have $k\cdot S(n,1)=k$; this is counting a certain number of applications, the ones that send every element of $X$ (taking $S(n,1)$ we are counting the trivial partition in $X$ that is just $X$) to a certain element of $Y$ (and there are $k$ of them because there are $k$ distinct elements in $Y$). Let's take now $j=2$: we will have ${k \choose 2}\cdot 2\cdot S(n,2)$, that counts the following: we would have ${k\choose 2}$ ways of picking $2$ elements of $Y$ (as $|Y|=k$); if we take a partition of two elements, we could send each subset to one of these two values previously selected, so for each partition of two elements we would have two applications, as we can send the first element of the partition to the first selected element of $Y$, and the second element of the partition to the secondly selected element of $Y$, and viceversa. So, as the number of partitions of two elements is $S(n,2)$, this case will be obtained. In general, I assume that I can think about having the case of partitions of $j$ elements, in which I would need ${k\choose j}$ elements of $Y$, and for each partition of this type, I would have $j!$ different applications (reordering the chosen elements of $Y$ would provide us with different applications: the first element of the partition will be sent to the first element among the selected ones in $Y$ stablished by the permutation ($j!$ is the number of permutations), and so on). So, in this certain case (partitions with $j$ elements), we would ``produce'' ${k\choose j}\cdot j!\cdot S(n,j)$ applications (as $S(n,j)$ is the number of possible permutations of this type). So, adding all this possibilites together will conclude the problem. I would appreciate if someone could tell me if my thoughts are well-organized, and if it is possible to make a more compact/elegant proof of this matter.

Thanks in advanced for all!

Answer 1

In terms of balls put into boxes:

• $S(n,j)$ is the number of different ways ways of putting $n$ labelled balls into $j$ unlabelled boxes so each of the $j$ boxes has at least one ball (by definition, the number of ways to partition a set of $n$ objects into $j$ non-empty subsets)
• $j! S(n,j)$ is the number of different ways ways of putting $n$ labelled balls into $j$ labelled boxes so each of the $j$ boxes has at least one ball (labelling the boxes means putting them in any of $j!$ orders)
• ${k \choose j}j! S(n,j)$ is the number of different ways ways of putting $n$ labelled balls into $k$ labelled boxes so exactly $j$ of the $k$ boxes has at least one ball (since there are ${k \choose j}$ ways of choosing the $j$ boxes with balls from the $k$ boxes)
• $\sum\limits_{j=1}^{k}{k \choose j}j! S(n,j)$ is the number of different ways ways of putting $n$ labelled balls into $k$ labelled boxes considering all the possible numbers of boxes which have at least one ball, providing $k \ge 1$
• But this is just the number of ways of putting $n$ labelled balls into $k$ labelled boxes, which is $k^n$, so $$\sum\limits_{j=1}^{k}{k \choose j}j! S(n,j)= k^n$$