Número de funciones on desde$Y$ a$X$ (JEE Advanced 2018)

Question

Deje $X$ ser un conjunto con $5$ elementos y $Y$ ser un conjunto con $7$ elementos. Si $\beta$ es el número de a las funciones de $Y$ a $X$ , entonces el valor de $\dfrac{\beta}{5!}$ es?

Mi planteamiento es:

Primero le doy a cada elemento de a$Y$ uno de los elementos de $X$ , que luego me deja con dos posibilidades para los dos elementos restantes de $Y$.

1) Ambos pueden tomar el mismo valor

2) Ambos tienen diferente valor de X.

Por lo que el número de en funciones = $\beta = {^7}C_5\times 5! \times(5+ 5\times4)$ , pero esto es incorrecto.

¿Cuál es mi error?

Además, sé cómo solucionar el problema mediante el principio de inclusión y exclusión que se da la respuesta correcta, pero no se nos dan las calculadoras en el examen y el cálculo de los involucrados no es muy largo.

Answer 1

Su método cuenta cada surjective función que se asigna a tres elementos de la $Y$ a un elemento de $X$ tres veces, una para cada forma de designar a uno de esos tres elementos, como el elemento de $Y$ que se asigna a ese elemento de $X$.

Por ejemplo, considere la surjective función de $f: Y \to X$ definido por $f(1) = 1$, $f(2) = 2$, $f(3) = 3$, $f(4) = 4$, $f(5) = f(6) = f(7) = 5$. Usted contar con esta función tres veces:

$$\begin{array}{c | c} \text{designated ordered pairs} & \text{additional ordered pairs}\\ \hline (1, 1), (2, 2), (3, 3), (4, 4), (5, 5) & (6, 5), (7, 5)\\ (1, 1), (2, 2), (3, 3), (4, 4), (6, 5) & (5, 5), (7, 5)\\ (1, 1), (2, 2), (3, 3), (4, 4), (7, 5) & (5, 5), (6, 5)\\ \end{array}$$ donde hemos escrito $(y, x)$ si $f(y) = x$.

Que cuente cada surjective función que se asigna a dos elementos de la $Y$ a un elemento de $X$ y otros dos elementos de $Y$ a un elemento diferente de $X$ cuatro veces, dos veces para cada par de elementos de a$Y$ que se asignan a un único elemento de $X$.

Por ejemplo, considere la surjective función de $f: Y \to X$ definido por $f(1) = 1$, $f(2) = 2$, $f(3) = 3$, $f(4) = f(6) = 4$, $f(5) = f(7) = 7$. Usted contar con esta función de cuatro tiempos:

$$\begin{array}{c | c} \text{designated ordered pairs} & \text{additional ordered pairs}\\ \hline (1, 1), (2, 2), (3, 3), (4, 4), (5, 5) & (6, 4), (7, 5)\\ (1, 1), (2, 2), (3, 3), (6, 4), (5, 5) & (4, 4), (7, 5)\\ (1, 1), (2, 2), (3, 3), (4, 4), (7, 5) & (6, 4), (5, 5)\\ (1, 1), (2, 2), (3, 3), (6, 4), (7, 5) & (4, 4), (5, 5)\\ \end{array}$$

Vamos a corregir su cuenta.

Surjective funciones en las que exactamente tres elementos de $Y$ mapa a un solo elemento de $X$: Elegir el que tres de los siete elementos de la $Y$ mapa a un solo elemento de $X$. Elija este elemento de la $X$. Ya que la función es surjective, el resto de los cuatro elementos se debe asignar a elementos distintos del resto de los cuatro elementos de la $X$. El número de tales funciones es $$\binom{7}{3}\binom{5}{1}4!$$

Surjective funciones en las que exactamente dos elementos de la $Y$ mapa a un solo elemento de $X$ y exactamente a otros dos elementos de $Y$ mapa a un elemento diferente de $X$: Elija la que dos de los cinco elementos de la $X$ son cada una de las imágenes de los dos elementos de la $Y$. Elija el que dos de los siete elementos de la $Y$ mapa al más pequeño de estos elementos de $X$. Elija el que dos de los cinco restantes elementos de $Y$ mapa más grande de estos elementos de $X$. Ya que la función es surjective, los tres restantes elementos de $Y$ se debe asignar a los distintos elementos de los tres restantes elementos de $X$. El número de tales funciones es $$\binom{5}{2}\binom{7}{2}\binom{5}{2}3!$$

Total: Puesto que los dos casos anteriores son mutuamente excluyentes y exhaustivos, el número de surjective funciones de $Y$ a $X$ es $$\binom{7}{3}\binom{5}{1}4! + \binom{5}{2}\binom{7}{2}\binom{5}{2}3!$$

Answer 2

El error es que se overcounting algunos mapas. Por ejemplo (asumiendo $X=\{1,\dots,5\}$ e $Y=\{1,\dots,7\}$), el mapa que es la identidad en $X$ y mapas de $6,7\mapsto 1$ es contado varias veces. Una vez, eligiendo en primer lugar, los elementos $1,2,3,4,5$, y la asignación de los dos elementos restantes a $1$. Un segundo momento mediante la selección en su primer paso $6,2,3,4,5$ y, a continuación, asignar el resto de los elementos (1 y 7) a $1$. Un tercer momento mediante la selección de $7,2,3,4,5$ y, a continuación, asignar el resto de los elementos (1 y 6) a 1.

Usted puede ver que el surjective mapas mapa de los tres elementos para un mismo $x$ (el primer tipo en tu pregunta) se cuentan tres veces. Si usted puede averiguar cómo muchas veces usted cuenta que cada mapa de otro tipo (tipo 2 en tu pregunta), entonces usted puede arreglar su argumento.

Answer 3

Usted está overcounting. Tome $X = \{1,2,3,4,5\}$ e $Y = \{1,2,3,4,5,6,7\}$. A continuación, en su metodología, la elección de $5$ elementos de $Y$ y su asignación a todos los elementos en $X$, supongamos $f:Y \to X$ es una función tal que $f(1) = 1$, $f(2) = 2$,$f(3) = 3$,$f(4) = 4$,$f(5) = 5$ . A continuación, para $6$ e $7$, supongamos $f(6) = 1$ e $f(7) = 2$. Pero esta función es la misma como la siguiente: Vamos a $g:Y\to X$. Mientras que la elección de $5$ elementos de $Y$, elegimos $3,4,5,6,7$ y mapa de como $g(3) = 3$, $g(4) = 4$, $g(5) = 5$, $g(6) = 1$, $g(7) = 2$, que todavía es una asignación válida en su metodología. Entonces, para $1$ e $2$, el mapa de una manera que los $g(1) = 1$ e $g(2) = 2$. Ahora tenemos $f = g$ pero contamos tanto de ellos.

De esta manera, usted necesita encontrar el número de funciones que se cuentan varias veces y la cantidad de veces que se cuentan. Yo no sugieren que debido a que puede ser incluso más largo y es más fácil pasar por alto algunos de los casos.

El método que implica la Inclusión-Exclusión Principio nos lleva a Número de Stirling del Segundo Tipo. No estoy seguro de que le da una manera de contar con menos cálculos, pero se puede leer, también hay una fórmula de recursión, la cual podría ser útil.