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...

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).$$

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}.$$

• Could you share a link on a source with information about this method of solving the problem? – J.Exactor Oct 20 '15 at 0:10
• This MSE link also discusses the problem. – Marko Riedel Oct 20 '15 at 0:14