Hola
Entonces el número de aplicaciones sobreyectivas es:
\( m^n-{ m \choose 1 } \cdot (m-1)^n + { m \choose 2 } \cdot (m-2)^n + \codts +(-1)^n \cdot { m \choose m-1 } \).
Una biyección no tiene puntos fijos, sí \( \forall i \in A \ , \ f(i) \neq i \) donde donde \( f : A \to A \).
Para calcular el conjunto de aplicaciones biyectivas sin puntos fijos calculamos el complementario, el conjunto de aplicaciones que almenos tiene un punto fijo.
Sea \( B_i = \{ f :A \to A | f(i) = i \} \). donde \( f \) biyectiva.
Tenemos que \( |B_i | = (n-1)! \), generalizando \( | B_{i_1} \cap B_{i_2} \cap \cdots \cap B_{i_r} | = (n-r)! \).
Entonces \( B=\cup_{i=1}^n B_i \) usando el principio de inclusión exclusión:
\( |B| = n\cdot(n-1)! - { n \choose 2}\cdot (n-2)! + { n \choose 3} \cdot (n-3)! + \cdots + (-1)^n \cdot { n \choose n} (n-n)! \).
Como el número de aplicaciones biyectivas es \( n! \) tenemos que el número de aplicaciones sin puntos fijos es:
\( n! -n! + { n \choose 2}\cdot (n-2)! - { n \choose 3} \cdot (n-3)! + \cdots + (-1)^{n+1} \cdot { n \choose n} (n-n)! = \).
\( = { n \choose 2}\cdot (n-2)! - { n \choose 3} \cdot (n-3)! + \cdots + (-1)^{n+1} \cdot { n \choose n} (n-n)! = \).
\( = n! \cdot (\dfrac{1}{2!} - \dfrac{1}{3!} +\cdots (-1)^{n+1} \dfrac{1}{n!}) \).
Hasta aquí de acuerdo en todo.
Finalmente el número que tu pides es :
\( n! \cdot (\dfrac{1}{2!} - \dfrac{1}{3!} +\cdots (-1)^{n+1} \dfrac{1}{n!}) \cdot m^{n-m} \).
Aquí no; pareciera que estás razonando que una aplicación sobreyectiva sin puntos fijos se contruye con una biyectiva sin puntos fijos entre los \( m \) primeros elementos y luego eligiendo las imágenes de los \( n-m \) restantes.
Pero esto no tiene porque ser así. La aplicación restringida a los \( m \) primeros elementos no tiene porque ser sobreyectiva ya que la sobreyectividad podría conseguirse con los \( n-m \) restantes.
Que debería ser igual a:
\( m^n - { m \choose 1 } \cdot (m-1)^n + { m \choose 2 } \cdot (m-2)^n + \codts +(-1)^n \cdot { m \choose m-1 } - n\cdot(n-1)! - \)
\( - ({ n \choose 2}\cdot (n-2)! + { n \choose 3} \cdot (n-3)! + \cdots + (-1)^n \cdot { n \choose n} (n-n)!)\cdot (m^{n-m}) \).
Ahí no entiendo lo que has hecho.
Yo propongo un camino similar al que has hecho para contar todas las aplicaciones sobreyectivas.
El número total de aplicaciones sin puntos fijos (sobreyectivas o no) es:
\( (m-1)^m\cdot m^{n-m} \)
ya que los \( m \) primeros elementos pueden tener cualqueir imagen menos ellos mismos y los demás cualquier imagen.
Ahora le restamos aquellas aplicaciones sin puntos fijos donde la imagen son a lo sumo \( m-1 \) elementos. Hay \( \displaystyle\binom{m}{1} \) formas de elegir el elemento que queda fuera. Serían:
\( \displaystyle\binom{m}{1}(m-2)^{m-1}(m-1)^{n-m+1} \)
Siguiendo el principio de inclusión-exlcusión ahora les tenemos que sumar las aplicaciones donde la imagen son a lo sumo \( m-2 \) elementos:
\( \displaystyle\binom{m}{2}(m-3)^{m-2}(m-2)^{n-m+2} \)
En definitiva queda:
\( \displaystyle\sum_{k=0}^{m-1}{}\displaystyle\binom{m}{k}(-1)^k(m-k-1)^{m-k}(m-k)^{n-m+k} \)
Saludos.
