Número de funciones

Question

Si $A=\left\{1,2,3,4,5\right\}$

Encontrar el Número de funciones de $f : A \to A$ tal que $f(f(x))=f(x)$

Caso $1.$ si $f$ es inyectiva entonces $f(f(x))=f(x)$ $\implies$ $f(x)=x$, por lo tanto, no es sólo una función inyectiva, que es una función identidad.

Caso $2.$ Al $f$ es de varios a una función

Supongamos que $f(1)=f(2)=f(3)=f(4)=f(5)=k$, claramente por cualquier $k$ a partir del conjunto $A$, $f(f(x))=f(x)$

por lo tanto, hay cinco de estas funciones.

Hay otras posibilidades?

Answer 1

Esta propiedad es, en general, se llama idempotence. La página vinculada se da un argumento para contar el número de idempotente funciones de $f:\{1,\dots,n\}\to \{1,\dots,n\}$, lo que voy a copiar a continuación:

Una única operación $f: \{1,\dots,n\}\to \{1,\dots,n\}$ es idempotente si se asigna a cada elemento de a $\{1,\dots,n\}$ a un punto fijo de $f$. Podemos crear una partición de un conjunto con $n$ elementos en $k$ elegido puntos fijos y $n-k$ sin puntos fijos, y, a continuación, $k^{n-k}$ es el número de diferentes idempotente funciones. Por lo tanto, teniendo en cuenta todas las posibles particiones, $$\sum _{k=0}^{n}{n \choose k}k^{n-k}$$

En particular, para $n = 5$, obtenemos $196$. Esto se compara con el número total de funciones de $f:\{1,\dots,5\}\to\{1,\dots,5\}$, $|\{1,\dots,5\}|^{|\{1,\dots,5\}|} = 3125$

Answer 2

Hay otras posibilidades. Aquí hay uno:

1 pasa a 2

2 se va a 2

3 va a 5

4 va para 5

5 va para 5

---

Para ampliar esta respuesta: El marco de estas funciones es tener un cierto número (al menos uno) de los puntos fijos, y todo lo demás mapa en el conjunto de puntos fijos.

Answer 3

Deje $B_f = \{x\in A:f(x)=x\}$ $C_f= \{x\in A: f(x)\ne x\}.$

Para cada $x\in C,$ igualdad $f(f(x)) = f(x)$ implica que el $f(x)\in B.$

Por lo tanto, podemos elegir una función de la satisfacción de $f(f(x))=f(x)$ por

• la elección de un conjunto de $\varnothing\ne B \subseteq A,$ y, a continuación,
• la elección de una función de $f$ $C=A\smallsetminus B$ a $B.$

El número de maneras de elegir un subconjunto no vacío de a $A$ $2^{|A|}-1 = 2^5-1 = 31.$ El número de maneras de elegir un subconjunto de cualquier tamaño en particular $k\in\{1,\ldots,n\} = \{1,\ldots,5\}$ $\dbinom n k = \dbinom 5 k.$

El número de formas de elegir una función de $C$ a $B$ $|B|^{|C|} = |B|^{|A|-|B|} = |B|^{5-|B|}.$

Así que el número que buscamos es $$ \sum_{k=1}^n \binom n k k^{5-k} = \sum_{k=1}^5 \binom 5 k k^{5-k} = 5 + 80 + 90 + 20 + 1. $$