Cuántos surjective funciones están allí desde el $A=${$1,2,3,4,5$} a $B=${$1,2,3$}?

Question

Quiero saber cuántas surjective funciones a partir del conjunto $A=${$1,2,3,4,5$} para el conjunto de $B=${$1,2,3$}? Creo que la mejor opción es contar todas las funciones ($3^5$) y luego restar el no surjective funciones. Sin embargo, no estoy seguro de cómo puedo contar con estas funciones.

Gracias

Answer 1

Voy a mostrar dos maneras.

Primero es con su actual enfoque y el uso de la inclusión-exclusión, por lo que necesita para contar el número de funciones que se pierde exactamente $1$ elemento, vamos a llamarlo $S_1$ que es igual a ${ 3 \choose 1 }2^5 = 96$, y el número de funciones que se pierda exactamente $2$ elementos, llame a $S_3$,${3 \choose 2}1^5 = 3$. Y ahora el número total de surjective funciones es $3^5 - 96 + 3 = 150$.

Pero también se puede hacer la siguiente, arreglar un surjective función de $f$ y considerar los conjuntos de $f^{-1}(1), f^{-1}(2), f^{-1}(3)$. Debido a $f$ es surjective, partición de $A$ a $3$ distinto, no vacía de conjuntos.

Ahora creo que al revés, empezar con $A$ y la partición en $3$ disjuntos no vacíos conjuntos, decir $A_1, A_2, A_3$, a continuación, puede formar un surjective función sólo de la asignación de uno de los $A_i$ a uno de los elementos en $B$. El número de formas de dividir un conjunto de $n$ elementos en $k$ disjuntos no vacíos conjuntos de los números de Stirling del segundo tipo, y el número de maneras de asignar el $A_i$ a los elementos de la $B$ $k!$ (donde $k$ es el tamaño de $B$), en su caso particular, esto da $3!S(5,3) = 150$.

La razón por la que les mostré de estas dos maneras, es que usted puede utilizar para demostrar la "explícita" la fórmula de los números de stirling del segundo tipo, que es $$ k!S(n,k) = \sum_{i=0}^k (-1)^{k-i}{k \choose j} j^n $$ Con un simple doble conteo, y el uso más general de la inclusión de la exclusión, y por lo que yo sé, este es uno de los más "explícita" fórmulas que se pueden obtener.