Número de funciones de surjective de A a B

Question

Estoy en el camino correcto? No estoy seguro acerca de mi razonamiento...

Número de surjective funciones de $A$ $B$

$$A = \{1,2,3,4\} ; B = \{a,b,c\}$$

Debemos contar el surjective funciones, significado de las funciones para las que, para todos los $b \in B$, $\exists~a \in A$ tal que $f(a) = b$, $f$ siendo una de esas funciones. Para que una función de $f:A\rightarrow B$ a ser un surjective función, todos los 3 elementos de $B$ debe ser asignada.

Necesitamos contar cuántas maneras podemos hacer un mapa de los 3 elementos. Vamos a restar el número de funciones de $A$ $B$que sólo los mapas de 1 o 2 elementos de $B$ el número de funciones de $A$ $B$(calculada en 4.c : 81).

Sólo 1 elemento de $B$ es asignado

El primer $a \in A$ tiene tres opciones de $b \in B$. Los demás, a continuación, sólo tiene uno. Total de funciones de $A$ $B$la asignación a un solo elemento de $B$ : 3.

Exactamente 2 elementos de $B$ se asignan

Del mismo modo, hay $2^4$ funciones de $A$ $B$la asignación a 2 o menos $b \in B$. Sin embargo, estas funciones son las que se asignan a sólo 1 elemento de $B$. Así que hay $2^4-3 = 13$ funciones de respetar la propiedad que estamos buscando.

En el extremo, hay $(3^4) - 13 - 3 = 65$ surjective funciones de$A$$B$.

Answer 1

$$\left\lbrace{4\atop 3}\right\rbrace=6$$ is the number of ways to partition $ A$ into three nonempty unlabeled subsets. For each partition, there is an associated $ 3!$ number of surjections, (We associate each element of the partition with an element from $ B $). Por lo tanto, el número total de supresiones es$3! \times \left\lbrace{4\atop 3}\right\rbrace= 36$

Answer 2

De manera más general, el número de S(a,b) de surjective funciones a partir de un conjunto A={1,...,un} en un conjunto B={1,...,b} puede ser expresada como una suma :

$S(a,b) = \sum_{i=1}^b (-1)^{b-i} {b \choose i} i^a$

donde ${b \choose i} = \frac{b!}{i! (b-i)!}$ es el número de formas diferentes de elegir me los elementos en un conjunto de b elementos.

Para ver esto, observe primero que $i^a$ cuenta el número de funciones de un conjunto de tamaño $a$ a un conjunto de tamaño $i$. Por lo tanto, nuestro resultado debe estar cerca de la $b^a$ (que es el último término en nuestro sum). Si queremos mantener sólo surjective funciones, tenemos que eliminar las funciones que ir sólo a un subconjunto de tamaño $b-1$$B$. Hay ${b \choose {b-1}}$ estos subconjuntos, y para cada uno de ellos hay $(b-1)^a$ funciones. Si seguimos $b^a - {b \choose {b-1}} (b-1)^a$ como resultado de ello, hay algunas funciones que hemos eliminado más de una vez, es decir, todas las funciones que ir a un subconjunto de tamaño $< b-1$. Por lo tanto, tenemos que añadir, etc. Esto lleva a que el resultado afirmó: $b^a - {b \choose {b-1}} (b-1)^a + {b \choose {b-2}} (b-2)^a - ...$

Answer 3

Esta es una vieja cuestión, pero recientemente me encontré con el mismo problema y resuelto de una manera diferente que me parece un poco más fácil de comprender.

Digamos que tienes un $k$ letra del alfabeto, y desea encontrar el número de palabras posibles con $n_1$ repeticiones de la primera carta, $n_2$ de la segunda, etc. La ecuación para el número de palabras posibles es, como se ha demostrado en este documento:

$$ P(n:n_1,n_2,...,n_k)=\frac{n!}{n_1!\veces n_2! \times\cdots\times n_k!} $$

Ahora, piense en los elementos de $B$ como nuestro alfabeto de 3 letras, uno de los cuales se repiten en su asignación a los 4 elementos de la $A$. Desde la letra repetida podría ser cualquiera de $a$, $b$, o $c$, tomamos la $P(4:1,1,2)$ tres veces. A continuación, el número de surjections es

$$ 3\times P(4:1,1,2)=36 $$

Salí con la misma solución que el aceptado la respuesta, pero todavía puede ser errónea en algún lugar de mi razonamiento. Por favor, hágamelo saber si usted ve un error ;)