# Composition of Derangements

What is the probability that composing two random derangements yields another derangement?

A slightly more specific question: suppose we start with a given derangement and compose it with all derangements. What is the distribution of cycle structures?

Addendum: perhaps it would be worth explaining why this question popped up in the first place. I am interested (purely out of curiosity) in the expected number of "steps" it takes to reach the identity permutation where each step is composition with a random derangement. See here for a related question (the only different is starting with a random permutation).

If you like to have "context": this is like asking how many steps it takes for $n$ penguins/koalas/beings with terrible memory to find their room, which they will recognize upon being inside, but which is otherwise indistinguishable. That's why I originally began with an arbitrary permutation, in any case.

• Derangement is a permutation without fixed points, right? – Fedor Petrov Nov 1 '16 at 6:17

An array of $k$ permutations of $n$ letters such that each pair are derangements of each other is a $k\times n$ Latin rectangle. If $L(k,n)$ is the number of $k\times n$ Latin rectangles, then the probability you ask for is $n!\, L(3,n)/L(2,n)^2$. The value of $L(2,n)$ is $n!$ times the number of derangements. The value of $L(3,n)$ doesn't have closed form but there are recurrences and summations; see here for a survey. The asymptotic value of $L(k,n)$ is $e^{-\binom k2} (n!)^k$ for fixed $k$, from which you can see that the asymptotic value of the probability is $e^{-1}$.
• It's interesting that the asymptotic probability is the same as the asymptotic probability a random permutation is a derangement. Composing two random derangements does not give a random permutation though - the identity has probability $1/D_n$ of appearing. – cats Nov 1 '16 at 15:01
• It seems to be minimised for $n=5$ at a probability of $\frac{69}{242} \approx 0.285$. – Henry Nov 1 '16 at 15:23