Número de funciones que $f(f(f(x)))=x$

Question

El problema es:

Para $f:X\rightarrow X$ donde $X$ $n$ elementos distintos, żcuántos $f$ existen que cumplan $f(f(f(x)))=x$ todos los $x\in X$?

Puedo calcular para el pequeño número de $n$'s de la siguiente forma (por ejemplo, $n=8$):

caso 1) $f$ es una función identidad ( $f(x)=x$ )$x$.

caso 2) $f$ es una función identidad para los 5 elementos en $X$ y para el resto de los 3, es cíclico, es decir,$f(a)=b,f(b)=c,f(c)=a$.

caso 3) $f$ es una función identidad para 2 elementos en $X$ y para el resto de 6, se puede dividir en dos grupos cada uno con 3, y cada uno de los grupos cíclicos.

Como sólo hay dos maneras diferentes de ser cíclica (1,2,3 o 1,3,2), el número de funciones para $n=8$ puede ser calculado como:

$$1+\binom85\cdot2+\binom82\binom63\frac12\cdot2^2=1233$$

Yo también podría generalizar para cualquier $n$ como:

$$n=3m+p\quad (p=0,1,2)$$ $$a_n=\sum_{k=0}^m\left(\binom{n}{n-3k}\cdot2^k\cdot\frac1{k!}\prod_{i=0}^{k-1}\binom{n-3k}{3}\right)$$

Y luego me enteré de que $a_n$ $1,1,3,9,21,81,351,1233,\dots$ que es la secuencia en este enlace https://oeis.org/A001470/internal. En el enlace, se muestra una sencilla ecuación de recurrencia de

$$a_n=a_{n-1}+(n-1)(n-2)a_{n-3}$$

Pero yo no puedo entender cómo se puede llegar a la ecuación de recurrencia.

Así que mi pregunta es "¿cómo uno puede llegar a la anterior ecuación de recurrencia"?

Answer 1

Para entender la recurrencia, tenga en cuenta que una función en un conjunto de $n$ miembros pueden fijar bien el último miembro o no. Si el último miembro es fija, tiene una función en el primer $n-1$ de los miembros. Si el último miembro no es fijo, usted tiene $n-1$ opciones de la siguiente elemento en su ciclo, $n-2$ opciones para el tercer elemento en su ciclo, y una función en el resto de las $n-3$ elementos.