The problem:

Find the recurrence formula for number of permutations if a cube of any such permutation is identity permutation.


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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.