Hola
Sean $$A$$ y $$B$$ conjuntos de cardinal $$n$$ y $$m$$, resoectivamente. Cuantas aplicaciones hay de $$A$$ a $$B$$ tal que su conjunto imagen tenga cardinal $$k$$ (suponed que $$k \leq{n,m}$$)
Llama \( A(n,k) \) al número de aplicaciones sobreyectivas de un conjunto de cardinal \( n \) sobre uno de cardinal \( k \). Dado que el conjunto \( B \) tiene \( \displaystyle\binom{m}{k} \) posibles subconjuntos de k elementos, el número total de aplicaciones en las condiciones que buscas es:
\( \displaystyle\binom{m}{k}A(n,k) \)
Ahora es un resultado bastante conocido que:
\( A(n,k)=\displaystyle\sum_{k=0}^n(-1)^k\displaystyle\binom{n}k(n-k)^m. \)
La idea de esta fórmula es:
1) Hay \( n^k \) aplicaciones de un conjunto de \( n \) elementos en otro de \( k \) elementos.
2) Como nos interesan las sobreyectivas le restamos las que han dejado al menos un elemento fuera de la imagen. Hay \( \displaystyle\binom{n}1 \) formas de elegir ese elemento y una vez elegido \( n^{k-1} \) aplicaciones posibles.
\( -\displaystyle\binom{n}1n^{k-1} \)
3) Pero hemos restado dos veces el número de aplicaciones que deja fuera un par de elementos dado. Por ejemplos las que dejan fuera de la imagen el \( 1 \) y el \( 2 \) las hemos contado como las que dejan fuera el \( 1 \) y después como las que dejan fuera el \( 2 \). Entonces se las volvemos a sumar. Las formas de elegir pares de elementos son \( \displaystyle\binom{n}2 \) y una vez elegido \( n^{k-2} \) aplicaciones posibles.
\( +\displaystyle\binom{n}2n^{k-2} \).
Reiterando el argumento usando el principio de inclusión exclusión se obtiene el resultado.
Saludos.
