Yo estaba tratando de calcular el número de surjective (a) funciones de la a a la B.
Vamos a un conjunto $A$ contienen $m$ elementos y otro conjunto $B$ contienen $n$ elemento decir
$$|A|=m, \quad |B|=n.$$
Ahora, si $n>m$, no. de en funciones es $0$.
Al $m \ge n$,
ya no debe haber ningún elemento no relacionado en B, deje que nosotros se relacionan los primeros n elementos de a a B,de modo que todos los elementos de B se presenta relacionados.
Por lo tanto el total de posibilidad para los primeros n elementos de a( que en realidad contienen m elementos ) se
$$n!$$
Ahora el resto de $m-n$ elementos en $A$ puede estar relacionado con cualquiera de las $n$ elementos de $B$. Por lo tanto el total de la posibilidad de que el resto de los $m-n$ elementos de $B$ es
$$n^{m-n}$$
Por lo tanto, el número total de surjective función es$$n!*n^{m-n}$$
Está nada mal en este cálculo ?Si su mal , ¿puede alguien sugerir método correcto con la prueba.
Respuestas
¿Demasiados anuncios?
En general, calcular el número de surjections entre conjuntos finitos es difícil.
El procedimiento para la obtención de la cifra de $n! \cdot n^{m-n}$ es overcounting, y también errónea por otra razón.
- Es overcounting porque está especificando un par ordenado de funciones (una bijective, uno arbitrario) que juntar para formar una surjection $A \to B$, pero en general hay muchas maneras de dividir un surjection en un bijection y una función arbitraria.
- También es erróneo, ya que parte de su procedimiento consiste en "el primer $n$ elementos' de $A$, lo que significa que usted ha elegido un distinguido subconjunto de $A$ del tamaño de la $n$. Hay $\binom{m}{n}$ maneras de hacer esto, por lo que su procedimiento debería, de hecho, el rendimiento de $\binom{m}{n} \cdot n! \cdot n^{m-n}$. Pero aún así overcounting: se cuenta el número de ordenadas triples $(A',f,g)$ donde $A' \subseteq A$ es un subconjunto con $n$ elementos, $f : A' \to B$ es un bijection y $g : A \setminus A' \to B$ es una función arbitraria.
Incluso calcular el número de surjections $A \to B$ al $n(A)=m$ $n(B)=3$ es bastante complicado. Hay $3^m - 3 \cdot 2^m + 3$ de ellos (ver aquí, por ejemplo).
Si recuerdo correctamente, no se conoce la forma cerrada de la expresión para el número de surjections a partir de un conjunto de tamaño $m$ a un conjunto de tamaño $n$.
Usted puede escribir una expresión mediante la inclusión-exclusión. Hay $n^m$ total funciones de$A$$B$. Restar fuera de los que no alcanzan a cubrir uno de los elementos. Hay $(n-1)^m$ que omitir un elemento particular, por lo que se podría restar $n(n-1)^m$ a eliminar los que no omitir algún elemento. Se han eliminado todos aquellos que pasar dos elementos de dos veces, así que tenemos que añadir de nuevo. Hay ${n \choose 2}(n-2)^m$ que pasar dos elementos. Ahora hemos eliminado los que saltar tres elementos, tres veces, y agregó volver tres veces, así que tenemos que restar ${n \choose 3}(n-3)m$. La expresión final es $$n^m+\sum_{i=1}^{n-1}(-1)^i{n \choose i}(n-i)^m$$
El número de surjections de un conjunto de elementos de #% de #% % a un conjunto de elementos de #% de #% % es $m$ $ $n$ Dónde está un número de Stirling de segunda especie.
