Hola,
Esa fórmula se puede demostrar por un lugar bastante interesante, sin utilizar la inducción. El 99% de la demostración sale de demostrar la fórmula para el cálculo de las funciones sobreyectivas de un dominio de n elementos en un codominio de m elementos:
\( Sob(n,m) = \displaystyle\sum_{k=0}^m{(-1)^k\displaystyle\binom{m}{k}(m-k)^n} \)
Esta parte de la dem sale no muy complicada, solo basta aplicar el principio de inclusión-exclusión (para contar el cardinal de conjuntos). Esta identidad está también relacionada con los números de Stirling de 2nda clase.
Luego de la primera parte, resta hacer una pequeña observación, cuántas funciones sobreyectivas habrá de un conjunto de n elementos en otro de n elementos? Evidentemente, habrá n!. Por lo tanto:
\( Sob(n,n) = n! = \displaystyle\sum_{k=0}^n{(-1)^k\displaystyle\binom{n}{k}(m-k)^n} \)
Como se quería probar. Si tengo tiempo y les interesa, un dia de estos pongo la prueba de la primera parte.
Saludos.