The problem:
Find the recurrence formula for number of permutations if a cube of any such permutation is identity permutation.
Solving:
We have to count the number of permutations $\pi$ such that $\pi ^ 3 = e$. All such permutations may be presented as products of cycles with length $1$ or $3$.
Let $f(n)$ be the number of such permutations on the set $\{1,…,n\}$.
Let's consider the set $\{1\}$. We see that $f(1) = 1$, because the permutation is $(1)$.
Let's consider the set $\{1,2\}$. Now we can form permutation $(1)(2)$. Therefore $f(2) = 1$.
Now consider the set $\{1,2,3\}$. We can form 3 permutations: $(1)(2)(3)$, $(123)$, $(132)$ such that the cube of each permutation is the identity permutation. And so $f(3) = 3$.
And so on…
Best Answer
For the recurrence, consider a "good" permutation $\pi$ of the set $\{1,2,\dots,n,n+1\}$. Maybe $\pi$ takes $n+1$ to itself. There are $f(n)$ such good permutations, since $\pi$ restricted to $\{1,2,\dots,n\}$ can be any good permutation of $\{1,2,\dots,n\}$.
Or maybe $\pi$ takes $n+1$ to something else, say $i$. There are $n$ choices for $i$. And then $\pi$ must take $i$ to some $j\ne i$ between $1$ and $n$. There are $n-1$ choices for $j$. And then $j$ must be taken to $n+1$.
We are left with $n-2$ objects, which have $f(n-2)$ good permutations. Thus $$f(n+1)=f(n)+(n)(n-1)f(n-2).$$