Funciones de recuento entre dos conjuntos

Question

Tenemos esta pregunta en los deberes (disculpen mi mala traducción):

Esta pregunta trata de las funciones de recuento entre dos conjuntos:

A. ¿Cuántas funciones existen entre el conjunto $[1,2,...,n]$ y el conjunto $\{1,2\}$ ? ¿Cuántos de ellos son en ?

B. ¿Cuántas funciones existen entre el conjunto $\{1,2\}$ y $[1,2,...,n]$ ? ¿Cuántos de ellos son inyectiva ?

Realmente no sé por dónde empezar. He probado a sumar el coeficiente binomial, pero se repiten los conjuntos. ¿Alguna idea para ponerme en marcha? Gracias.

Answer 1

El número de funciones de un conjunto $X$ a otro conjunto $Y$ viene dada por $|Y|^{|X|}$ ya que cada elemento del conjunto $X$ tiene $|Y|$ opciones.

Por lo tanto, en el primer caso, tiene un total de $2^n$ funciones. Para contar el número de funciones onto (sobreyectivas), la forma más fácil en este caso es restar el número de funciones que no son onto. En este caso, sólo hay dos funciones que no son onto, a saber, la función que mapea cada elemento a $1$ y la otra función que asigna cada elemento a $2$ . Por lo tanto, el número total de funciones onto es $2^n-2$ .

En el segundo caso, el número total de funciones es $n^2$ . Para contar el número de funciones uno a uno (inyectivas), todo lo que necesitamos es $1$ y $2$ debe corresponder a elementos distintos. Si la función es uno-a-uno, entonces el número de opciones para $1$ es $n$ . Una vez que sepamos dónde $1$ se ha asignado al número de opciones para $2$ para que la función sea uno a uno, es $n-1$ . Por lo tanto, el número total de funciones inyectivas es $n(n-1)$ .

Answer 2

A. Si $f$ es una función de $\{1,\cdots,n\}$ y $\{1,2\}$ que básicamente significa que para cada elemento $a$ en $\{1,\cdots,n\}$ podemos "marcarlo" (asignarlo a 1) o no (asignarlo a 2). En total tenemos $2^n$ casos.

Espero que eso ayude.

Answer 3

El número total de funciones uno a uno para establecer $A$ del conjunto $B$ se calcula mediante la fórmula:

$$_nP_m =\frac{n!}{(n-m)!}$$

donde $m$ es la cardinalidad del conjunto $A$ y $n$ es la cardinalidad del conjunto $B$ . Y $m\leq n$ .

Answer 4

Para el segundo caso

1. 1 tiene $n$ opciones
2. 2 tiene $n-1$ opciones
3. estos dos del segundo conjunto pueden ser seleccionados por $nC2$ la fórmula final es $2n(n-1)$