Recurrence forlmula for number of permutation. 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...
 A: 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).$$
A: The combinatorial species here is $$\mathfrak{P}(\mathfrak{C}_{=1}(\mathcal{Z}) + \mathfrak{P}(\mathfrak{C}_{=3}(\mathcal{Z})).$$
This yields the generating function $$G(z) = \exp(z+z^3/3)$$ where $[z^n] G(z) = Q_n/n!$ with $Q_n$ the desired quantity.
Differentiate to obtain $$G'(z) = G(z) (1+z^2).$$
Extracting coefficients we get
$$Q_{n+1}/n! = Q_n/n! + Q_{n-2}/(n-2)!.$$
Multiply by $n!$ to obtain
$$Q_{n+1} = Q_n +  n(n-1)Q_{n-2}.$$
