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"?
