¿Cuántas funciones sobreyectivas existen desde A = {1,2,3,4,5} hasta B = {1,2,3}?

Answer 1

Para crear una función de A a B, para cada elemento en A debe elegir un elemento en B.

Hay 3 formas de elegir cada uno de los 5 elementos = [matemáticas] 3 ^ 5 [/ matemáticas] funciones.

Pero queremos funciones sobreyectivas. Entonces tenemos que deshacernos de las funciones que no se asignan a todos los elementos en B.

Hay [math] 3 * (2 ^ 5 – 2) [/ math] funciones donde se ignora 1 elemento de B. (Tiene 3 opciones para elegir qué elemento ignorar, y con los dos elementos restantes, puede hacer 2 ^ 5 funciones. De estas 2 ^ 5 funciones, 2 funciones usarán solo 1 elemento, por lo que podemos ignorarlas porque desea funciones que utilicen estrictamente 2 elementos, de modo que el total es [matemática] 3 * (2 ^ 5 – 2) [/ matemática]

Hay [matemática] 3 * 1 = 3 [/ matemática] funciones en las que se ignoran 2 elementos de B (3 opciones para las cuales 2 elementos ignorar y 1 función con el 1 elemento restante)

Entonces la respuesta es [matemáticas] 3 ^ 5 – 3 * (2 ^ 5-2) – 3 = 243 – 3 (30) – 3 = 150 [/ matemáticas]

Answer 2

Para cada subconjunto [math] C \ subseteq B [/ math], sabe que hay funciones [math] | C | ^ 5 [/ math] de [math] A [/ math] con el rango CONTENIDO en [math] C [ /matemáticas]. En particular, para cada uno de los tres conjuntos con 1 elemento, hay 1 función cuyo rango contiene solo ese elemento; y para cada uno de los tres pares de elementos, hay 32 funciones cuyo rango está incluido en ese conjunto, de las cuales 2 tienen un rango que es solo 1 elemento y 30 tienen un rango que incluye ambos elementos. Por lo tanto, hay funciones [math] 3 \ cdot 30 + 3 \ cdot 1 = 93 [/ math] cuyo rango contiene 1 elemento o 2 elementos. Como hay [math] 243 [/ math] funciones en total, las [math] 243 – 93 = 150 [/ math] otras funciones deben tener los 3 elementos de [math] B [/ math] en su rango.

Podríamos decir esto un poco más agradablemente con el principio de inclusión / exclusión, pero para un conjunto tan pequeño, esto es probablemente lo suficientemente simple.

Answer 3

Una sobreposición de un conjunto [matemática] A [/ matemática] de tamaño [matemática] n [/ matemática] a un conjunto [matemática] B [/ matemática] de tamaño [matemática] k [/ matemática] puede caracterizarse por una partición de [matemáticas] A [/ matemáticas] en subconjuntos de [matemáticas] k [/ matemáticas], junto con una permutación de los elementos [matemáticas] k [/ matemáticas] de [matemáticas] B [/ matemáticas]. Las particiones se cuentan por los números de Stirling del segundo tipo [matemáticas] S (n, k) [/ matemáticas], y las permutaciones se cuentan por [matemáticas] k! [/ Matemáticas], por lo que hay
[matemáticas] S (n, k) k! = \ sum_ {i = 0} ^ k (-1) ^ i \ binom ki (k – i) ^ n [/ math]
surjections. En este caso, eso es [matemática] S (5, 3) 3! = 6 \ cdot 25 = 150 [/ matemáticas].