¿Cómo relacionar el número de todas las aplicaciones X→YX→YX\to Y con los números de Stirling del segundo tipo?

Estoy estudiando los números de Stirling del segundo tipo y acabo de ver por qué$S(n,k)=\frac{1}{k!}\sum_{j=0}^{k-1}(-1)^{j}{k\choose j}(k-j)^{n}$(sabiendo que$\sum_{j=0}^{k-1}(-1)^{j}{k\choose j}(k-j)^{n}$cuenta el número de funciones sobreyectivas de$X=\{x_{1},...,x_{n}\}$en$Y=\{y_{1},...,y_{k}\}$). Ahora bien, en mis notas aparece que podemos relacionar estos números de Stirling de segunda clase con el número de todas las aplicaciones$X\to Y$, nombrar$j$el cardenal de la imagen, por esta fórmula:

$$\begin{equation*} k^{n}=\sum_{j=1}^{k}{k\choose j}j!S(n,j) \end{equation*}$$ Y tengo algunos problemas para visualizarlo. Mi primer enfoque fue tratar de manipular la primera relación con las sobreyectivas, pero me quedé atascado. Entonces he pensado en tratar de leer lo que significa el lado derecho: Si$j=1$, tenemos$k\cdot S(n,1)=k$; esto es contar un cierto número de aplicaciones, las que envían cada elemento de$X$(tomando$S(n,1)$estamos contando la partición trivial en$X$eso es solo$X$) a un cierto elemento de$Y$(y aquí están$k$de ellos porque hay$k$elementos distintos en$Y$). tomemos ahora$j=2$: tendremos${k \choose 2}\cdot 2\cdot S(n,2)$, que cuenta lo siguiente: tendríamos${k\choose 2}$formas de escoger$2$elementos de$Y$(como$|Y|=k$); si tomamos una partición de dos elementos, podríamos enviar cada subconjunto a uno de estos dos valores previamente seleccionados, por lo que para cada partición de dos elementos tendríamos dos aplicaciones, ya que podemos enviar el primer elemento de la partición al primero seleccionado elemento de$Y$, y el segundo elemento de la partición al segundo elemento seleccionado de$Y$, y viceversa. Entonces, como el número de particiones de dos elementos es$S(n,2)$, se obtendrá este caso. En general, asumo que puedo pensar en tener el caso de particiones de$j$elementos, en los que necesitaría${k\choose j}$elementos de$Y$, y para cada partición de este tipo, tendría$j!$diferentes aplicaciones (reordenando los elementos elegidos de$Y$nos proporcionaría diferentes aplicaciones: el primer elemento de la partición se enviará al primer elemento entre los seleccionados en$Y$establecido por la permutación ($j!$es el número de permutaciones), y así sucesivamente). Entonces, en este caso determinado (particiones con$j$elementos), "produciríamos"${k\choose j}\cdot j!\cdot S(n,j)$aplicaciones (como$S(n,j)$es el número de posibles permutaciones de este tipo). Entonces, sumando todas estas posibilidades juntas se concluirá el problema. Agradecería si alguien pudiera decirme si mis pensamientos están bien organizados y si es posible hacer una prueba más compacta/elegante de este asunto.

¡Gracias de antemano por todo!