Solución:
Considere $ f ^ {- 1} (y) $, $ y en Y $. Este conjunto no debe estar vacío, independientemente de $ y $. Lo que está pidiendo es la cantidad de formas de distribuir los elementos de $ X $ en estos conjuntos.
El número de formas de distribuir m elementos en n conjuntos no vacíos viene dado por los números de Stirling del segundo tipo, $ S (m, n) $. Sin embargo, cada elemento de $ Y $ puede asociarse con cualquiera de estos conjuntos, por lo que obtiene un factor adicional de $ n! $: El número total debe ser $ S (m, n) n! $
Los números de Stirling tienen propiedades interesantes. Vale la pena echarles un vistazo por su propio bien.
Aquí hay una solución que no involucra los números de Stirling del segundo tipo, $ S (n, m) $. El número de funciones sobreyectivas desde un conjunto $ X $ con $ m $ elementos hasta un conjunto $ Y $ con $ n $ elementos es
$$ sum_ {i = 0} ^ {n-1} (-1) ^ i {n elija i} (ni) ^ m $$
o más explícitamente $$ {n elija 0} n ^ m – {n elija 1} (n-1) ^ m + {n elija 2} (n-2) ^ m – cdots pm {n elija n-2} 2 ^ m mp {n elija n-1} 1 ^ m $$
Comenzamos contando el número de funciones desde $ X $ hasta $ Y $, que ya se mencionó como $ n ^ m $. A continuación, restamos el número $ n (n-1) ^ m $ (aproximadamente el número de funciones que omiten uno o más elementos). Por supuesto, esta resta es demasiado grande, así que volvemos a sumar $ {n choose 2} (n-2) ^ m $ (aproximadamente el número de funciones que faltan 2 o más elementos). Pero, de nuevo, esta suma es demasiado grande, por lo que restamos el siguiente término y así sucesivamente. Este es un bosquejo aproximado de una prueba, podría hacerse más formal usando inducción en $ n $.
Esto da un recuento excesivo de las funciones sobreyectivas, porque su construcción puede producir la misma función en más de una forma.
Considere un caso simple, $ m = 3 $ y $ n = 2 $. Hay seis subconjuntos propios no vacíos del dominio, y cualquiera de estos puede ser la preimagen de (digamos) el primer elemento del rango, asignando posteriormente los elementos restantes del dominio al segundo elemento del rango. En otras palabras, hay seis funciones sobreyectivas en este caso.
Pero su fórmula da $ frac {3!} {1!} 2 ^ {3-2} = 12 $.
Adicional: Un recuento correcto de funciones sobreyectivas equivale a calcular números de Stirling del segundo tipo. La sección de Wikipedia en Twelvefold Way tiene detalles. Para valores pequeños de $ m, n $ uno puede usar el recuento por inclusión / exclusión como se explica en la parte final de estas notas de clase.