Calcular el número total de surjective funciones

Question

Es muy fácil calcular el número total de funciones de un conjunto $X$ $m$ elementos de un conjunto $Y$ $n$ elementos ($n^{m}$), y también el número total de funciones inyectiva ($n^{\underline{m}}$, lo que denota la caída factorial). Pero estoy pensando acerca de cómo calcular el número total de surjective funciones de $f\colon X \twoheadrightarrow Y $.

La manera en que yo pensaba de hacer esto es la siguiente: en primer lugar, ya que todos los $n$ elementos del codominio $Y$ necesitan ser asignada a elegir alguno de los $n$ elementos de la $m$ elementos de las $X$ asignarse uno-a-uno con la $n$ elementos de $Y$. Esto se traduce en $n!$ posibles emparejamientos. Pero el número de maneras de elegir a $n$ elementos de $m$ elementos es $\frac{m!}{(m-n)!\,n!}$, por lo que el número total de maneras de coincidencia de $n$ elementos en $X$ a ser uno-a-uno con la $n$ elementos de $Y$$\frac{m!}{(m-n)!\,n!} \times n! = \frac{m!}{(m-n)!}$.

Ahora tenemos 'cubierto' el codominio $Y$ $n$ elementos de $X$, el resto de los impares $m-n$ elementos de $X$ puede ser asignado a cualquiera de los elementos de $Y$, por lo que hay $n^{m-n}$ maneras de hacer esto. Por lo tanto creo que el número total de surjective funciones deben ser $\frac{m!}{(m-n)!} \, n^{m-n}$.

Es esto algo como correcto o he hecho un gran error aquí?

Answer 1

Considere la posibilidad de $f^{-1}(y)$, $y \in Y$. Este conjunto no puede ser vacío, independientemente de $y$. Lo que estás pidiendo es el número de maneras de distribuir los elementos de $X$ en estos conjuntos.

El número de maneras de distribuir los m elementos en n no vacía de conjuntos está dada por los números de Stirling del segundo tipo, $S(m,n)$. Sin embargo, cada elemento de a $Y$ puede estar asociada con cualquiera de estos conjuntos, por lo que recoger un factor adicional de $n!$: el número total debe ser $S(m,n) n!$

Los números de Stirling tienen propiedades interesantes. Son digno de la comprobación hacia fuera para su propio bien.

Answer 2

Aquí es una solución que no implique la libra Esterlina números de segundo tipo. El número de surjective funciones a partir de un conjunto $X$ $m$ elementos de un conjunto $Y$ $n$ elementos

$$ \sum_{i=0}^{n-1} (-1)^n{n \elegir i}(n-i)^m $$

o más explícitamente $$ {n \elegir 0}n^m - {n \elegir 1}(n-1)^m + {n \elegir 2}(n-2)^m - \cdots \pm {n \elegir n-2}2^m \mp {n \elegir n-1}1^m $$

Comenzamos contando el número de funciones de$X$$Y$, que ya se han mencionado a ser $n^m$. A continuación nos resta fuera de la número $n(n-1)^m$ (aproximadamente el número de funciones que se pierda uno o más elementos). Por supuesto, esto resta es demasiado grande por lo que podemos agregar de nuevo en ${n \choose 2}(n-2)^m$ (aproximadamente el número de funciones que perder 2 o más elementos). Pero, de nuevo, esta adición es demasiado grande, por lo que nos resta de la siguiente término y así sucesivamente. Este es un boceto de una prueba, podría ser más formal mediante el uso de la inducción en $n$.

Answer 3

Esto le da un sobre cuenta de la surjective funciones, debido a que su construcción puede producir la misma en función de más de una manera.

Considere un caso simple, $m=3$$n=2$. Hay seis vacío adecuado subconjuntos del dominio, y cualquiera de ellas puede ser la preimagen de (digamos) el primer elemento de la gama, a partir de entonces asignar el resto de los elementos del dominio con el segundo elemento de la gama. En otras palabras, hay seis surjective funciones en este caso.

Pero su fórmula da $\frac{3!}{1!} 2^{3-2} = 12$.

Agregado: Un número correcto de surjective funciones es equivalente al cálculo de los números de Stirling del segundo tipo. La Wikipedia bajo la sección Twelvefold manera tiene detalles. Para valores pequeños de a $m,n$ uno puede usar el conteo de inclusión/exclusión, como se explica en la parte final de estas notas de la conferencia.

Answer 4

si observamos el número de surjective funciones por [m,n] tenemos: [m+1,n]=n*([m,n]+[m,n-1]) [m,1]=1 y [m,n]=0 para n>m obtenemos los siguientes números distintos de cero: [2,1]=1 [2,2]=2 [3,1]=1 [3,2]=6 [3,3]=6 [4,1]=1 [4,2]=14 [4,3]=36 [4,4]=24 [5,1]=1 [5,2]=30 [5,3]=150 [5,4]=240 [5,5]=120 [6,1]=1 [6,2]=62 [6,3]=540 [6,4]=1560 [6,5]=1800 etc La recurrencia es fácil de entender Un nuevo miembro en el conjunto X ES "solo" en su "casa" en la Y establecer o NO ES "solo" Adán fórmula es correcta Los números de Stirling del segundo tipo no están involucrados aquí

Answer 5

puede ser la respuesta que se puede( n!*m!/n!(m-n)!*n^m-n)/2