Funciones de $A$ a $A$

Question

Dejemos que $A=\{1,2,3,4,5,6\}$ . ¿Cuántas funciones distintas hay de $A$ a $A$ tal que $f(f(f(n)))=n$ para todos $n\in A$ ?

Lo he intentado pero aún no consigo respuesta. Gracias.

Answer 1

En primer lugar, establezcamos las posibilidades del estructura del ciclo en esta permutación (es decir, la función biyectiva de $A$ a $A$ ).

Por supuesto, si $f(n) = n$ para todos $n$ Entonces, eso funciona.

Supongamos que no es así. Es decir, supongamos que hay un $a$ tal que $f(a) \neq a$ . Sea $b = f(a)$ . Tenga en cuenta que no podemos tener $f(b) = a$ o $f(b) = b$ (¿por qué?), así que debe haber un tercer elemento $c$ tal que $f(b) = c$ . Ahora, ¿qué pasa con $c$ ? Bueno, tenga en cuenta que $f(c) = f(f(f(a)))$ . Por lo tanto, debe ser el caso que $f(c) = a$ .

Es decir, nuestra función debe actuar sobre algún elemento $a$ a través del ciclo $a \to b \to c \to a$ .

Ahora, $f$ debe hacer algo con los elementos restantes $d,e,f$ . Según la lógica anterior, hay dos posibilidades: o bien $f(n) = n$ para $n = d,e,f$ o tenemos otro ciclo $d \to e \to f \to d$ .

Ahora: contemos.

¿De cuántas maneras podemos construir una permutación de dos ciclos $$ a \to b \to c \to a, \quad d \to e \to f \to d $$ Hay $6 \times 5 \times 4$ formas de seleccionar los elementos $a,b,c$ . Sin embargo, este método cuenta cada ciclo tres veces (por ejemplo, $1 \to 2 \to 3 \to 1$ es lo mismo que $2 \to 3 \to 1 \to 2$ ), por lo que hay $\frac{6 \times 5 \times 4}{3}$ formas de seleccionar el primer ciclo. Hay $3 \times 2 (\times 1)$ formas de seleccionar $d,e,f$ (habiendo seleccionado ya $a,b,c$ ), pero una vez más debemos dividir por $3$ . Por lo tanto, hay $\frac{6 \times 5 \times 4}{3} \times \frac{3 \times 2}{3}$ formas de seleccionar $2$ 3 ciclos sucesivamente. Esto cuenta cada permutación dos veces, así que dividimos por 2. En total, hay $$ \frac{6 \times 5 \times 4 \times 3 \times 2}{3 \times 3 \times 2} = 40 $$ formas de seleccionar dicha permutación.

Por un argumento similar, hay exactamente $$ \frac{6 \times 5 \times 4}{3} = 40 $$ formas de seleccionar una permutación con un $3$ -ciclo. Por último, también tenemos la función constante. En total, hay $$ 1 + 40 + 40 = 81 $$ con la propiedad deseada.

Answer 2

Cualquier $f$ debe ser $1$ -a- $1.$ Porque si $f(x)=f(y)$ entonces $x=f^3(x)=f^2(f(x))=f^2(f(y))=f^3(y)=y.$

Así que $f$ es una permutación de $\{1,...,6\}.$ Es decir, $f$ es una biyección.

Para $x\in \{1,..,6\},$ la secuencia $f^n(x)$ para $n=1,2,3,...(etc)$ debe contener duplicados. Si $f^n(x)=f^{n+m}(x)$ con $m>0,$ entonces, como $f^{-n}$ también es una biyección, tenemos $x=f^{-n}(f^n(x)) =f^{-n}(f^{n+m}(x))=f^m(x).$

Dejemos que $\|x\|$ denotan el menor $m>0$ tal que $f^{m}(x)=x.$ El conjunto $F(x)=\{f^j(x):1\leq j\leq \|x\| \}$ es un Ciclo de la Permutación $f.$

Tenemos $F(y)=F(x)\iff y\in F(x)$ y tenemos $F(y)\cap F(x)=\phi \iff F(y)\ne F(x)\iff y\not \in F(x).$ Así que $\{F(x):x\in \{1,...,6\}\;\}$ es una partición de $\{1,...,6\}.$

Para que $f^3(x)=x$ por cada $x,$ es necesario y suficiente que cada $F(x)$ tiene exactamente $1$ miembro o exactamente $3$ miembros.

(i). Si cada $F(x)$ acaba de $1$ miembro, entonces $f(x)=x$ para cada x. Esto da $1$ función de este tipo.

(ii). Si $F(x)$ acaba de $1$ miembro para cada uno de $3$ diferentes $x,$ y algunos $F(y)$ tiene $3$ miembros, hay $\binom {6}{3}=20$ particiones de este tipo. Y para cada partición de este tipo, hay exactamente $2$ permitido $f.$ ....Porque si $F(y)=\{y,z,a\}$ con $y\ne z\ne a \ne y$ entonces $f(y)=z, f(z)=a, f(a)=y$ o $f(y)=a,f(a)=z,f(z)=y$ .... Esto da $2\cdot\binom {6}{3}=40$ funciones de este tipo.

(iii). Si hay una serie de $F(x), F(y$ ) cada uno con $3$ miembros, hay $10$ particiones de este tipo.... Porque si $F(1)=\{1,a,b\}$ con $1\ne a\ne b \ne 1$ hay $\binom {5}{2}=10$ opciones para $\{a,b\}.$ Y para cada una de estas particiones, sólo hay $2$ opciones para $f(x).$ Y también sólo $2$ opciones para $f(y)$ y no dependen de la elección de $f(x).$ Así que hay $2^2\cdot 10=40$ funciones de este tipo.

En total tenemos $1+40+40=81$ funciones.