Preimagen de un tamaño específico

Question

Mi hijo tiene este problema en un curso de matemáticas discretas:

¿Cuántas funciones $f:\{1,2,3,4\}\to\{1,2,3,4\}$ tienen la propiedad de que, para todo $i$, la imagen inversa de $i$ no tiene tamaño $i$ (es decir, $\left|f^{-1}[\{i\}]\right|\ne i$)?

Por supuesto se pueden listar todas ellas, pero sospecho que hay una manera más elegante que no estoy viendo.

Answer 1

Dado que hay cierta confusión, daré mi respuesta también.

Aplicamos la inclusión-exclusión. Empezamos con las $4^4=256$ posibles funciones diferentes en total. Luego restamos aquellas que violaron la condición de que $1$ tenía una preimagen, aquellas que tenían que $2$ tenía dos preimágenes y así sucesivamente. Como parte de la inclusión-exclusión, luego sumamos aquellas que simultáneamente tenían una preimagen para $1$ y dos preimágenes para $2$ y así sucesivamente... notando que muchos de estos casos, incluidos aquellos que violarían simultáneamente tres o más condiciones, son imposibles.

Obtenemos:

$$256 - 4\cdot 3^3 - \binom{4}{2}\cdot 3^2 - \binom{4}{3}\cdot 3^1 - 1 + 4\cdot 3\cdot 2 + 4 = 109$$

El valor de $4\cdot 3\cdot 2$ en el ejemplo anterior correspondía a $1$ con una preimagen y $2$ con dos preimágenes. Esto se calcula eligiendo cuál es la preimagen de $1$ (4 opciones), eligiendo qué dos elementos son las preimágenes de $2$ ($\binom{3}{2}=3$ opciones), y luego para el elemento final eligiendo a dónde se mapea (2 opciones).

Esto coincide con el intento y la respuesta del OP.

Answer 2

Hay una función tal que la preimagen de 4 tiene un tamaño de 4.

Si la preimagen de 3 tiene un tamaño de 3, hay cuatro opciones para qué elemento no se asigna a 3, y dos opciones para a qué se asigna (por ahora ignoraré la posibilidad de que sea 1, lo cubriré más tarde), en total ocho funciones.

Si la preimagen de 2 tiene un tamaño de 2, hay seis opciones para qué elementos no se asignan a 2, y cinco opciones para a qué se asignan (por ahora ignoraré la posibilidad de que solo uno de ellos se asigna a 1, lo cubriré más tarde), en total treinta funciones.

Si la preimagen de 1 tiene un tamaño de 1, hay cuatro opciones para qué elemento se asigna a 1, y 27 opciones para las otras asignaciones, en total 108 funciones.

Por lo tanto, hay un total de $256-1-8-30-108=109$ funciones que cumplen con los criterios de la pregunta.

Mención especial: JMoravitz, en un comentario

Answer 3

Seamos particionar el conjunto de dominio y buscar mapas que satisfacen las condiciones dadas.

• $4=4.$ Todos los elementos se asignan a uno de $\{1,2,3\}$. $3$ funciones.
• $4=3+1.$ $3$ elementos se asignan a uno de $\{1,2,4\}$ mientras que $1$ elemento se asigna a uno que no ha sido usado de $\{2,3,4\}$. $28$ funciones.
• $4=2+2$. Dos elementos se asignan a dos de $\{1,3,4\}$. $18$ funciones.
• $4=1+1+1+1$. Un elemento se asigna a cada uno de $\{1,2,3,4\}$; esto no está permitido. $0$ funciones.
• $4=2+1+1$. Dos elementos se asignan a uno de $\{1,3,4\}$. Los dos restantes se asignan a dos que no han sido usados de $\{2,3,4\}$. $60$ funciones.

Esto da un total de $3+28+18+0+60=109$ funciones.