Contando 1:1 y en funciones

Question

Estoy enfrentado con las siguientes preguntas:

1) ¿cuántas funciones hay a partir de un conjunto de tamaño de 3 a un conjunto de tamaño 5? Cuántos de ellos son 1-a-1?

2) ¿cuántas funciones hay a partir de un conjunto de tamaño 10 a un conjunto de tamaño 2? Cuántos de ellos están en?

Intento:
1) Para determinar el número de funciones, podemos establecer$A = \{a,b,c\} = a$$B = \{d, e, f, g, h\} = b$. Por lo que el número de funciones es $b^a$ o $5^3$. Sin embargo, esta es una gran figura para mí, cada uno con papel y lápiz para determinar cuántos son 1:1. ¿Hay alguna forma sencilla?

2) Igual que la parte 1 pero no quiero escribir $2^{10}$ funciones para ver cuántos son en.

Answer 1

Estoy haciendo una función de $f$ a partir de un conjunto de $3$ elementos, decir que el conjunto de $A=\{a,b,c\}$, a un conjunto $B$ $5$ elementos.

Puedo elegir el valor de $f(a)$ $5$ maneras. Para cada modo de decidir lo $f(a)$ es, hay $5$ maneras de decidir lo $f(b)$, para un total de $5^2$ formas de decidir los valores de $f(a)$ e $f(b)$. Y para cada forma de hacerlo, hay $5$ opciones para el valor de $f(c)$, para un total de $5^3$.

Si queremos $f$ a ser de uno a uno, a continuación, para cada opción sobre el valor de $f(a)$, sólo tenemos $4$ opciones para $f(b)$, ya que no podemos tener $f(a)=f(b)$. Y una vez que hemos escogido $f(a)$$f(b)$, sólo hay $3$ valores permitidos para $f(c)$. Por lo tanto, hay $(5)(4)(3)$ uno a uno las funciones de$A$$B$.

Para el segundo problema, deje que nuestro $2$-element set $B$ ser, es decir, $\{0,1\}$. Hay, por el mismo argumento que antes, $2^{10}$ funciones de un conjunto $A$ $10$ elementos para el conjunto de $B$.

Cómo muchos de estos $2^{10}$ funciones son malas (no sobre)? Exactamente $2$ de ellos, la función que enviar a todo el mundo a $0$ y el que envía a todo el mundo a $1$.

Answer 2

Para el primer problema, tenga en cuenta que un 1-a-1 la función $f:X\to Y$ es la misma cosa como una opción de subconjunto $f(X)\subset Y$ del tamaño de la $|X|$, junto con una manera de hacer coincidir los elementos de $X$ con los elementos de la $f(X)$. De cuántas maneras existen para realizar cada una de estas cosas? (En respuesta a la segunda de estas podría ser más fácil si usted piensa de $X = \{1,2,\ldots,n\}$.)

Para el segundo problema, que me sugieren que es más fácil contar cuántas de esas funciones no sobre.

Answer 3

Una forma alternativa de contar funciones que están en: para cada elemento en el codominio, tienes que elegir algún elemento del dominio al mapa. Estos asignación a los elementos tienen que ser todos diferentes, así que para la primera, tienes todas las de $A$ a elegir, para el segundo tienes uno menos opciones, y así sucesivamente.

Una vez que tienes todos los elementos del codominio ser el destino de algo en el dominio, el resto del dominio puede asignar a donde quiera.