# What is the probability that two randomly selected derangements of order $n$ are derangements of each other?

First, let's acknowledge that if $$n=1$$ then $$P(A_1)=0$$, since there are no derangements of a set of order one; and if $$n=2$$, $$P(A_2)=0$$, since there is only one derangement of a set of order two. For $$n=3$$, the derangements of the set {$$1,2,3$$} are {$$2,3,1$$} and {$$3,1,2$$}. Since these are the only examples, and the 1st, 2nd, and 3rd digits are all different, the probability so far is $$P(A_3)=1$$.

Now take into account $$n=4$$. The derangements now are

1. {$$2,1,4,3$$}
2. {$$2,3,4,1$$}
3. {$$2,4,1,3$$}
4. {$$3,1,4,2$$}
5. {$$3,4,1,2$$}
6. {$$3,4,2,1$$}
7. {$$4,1,2,3$$}
8. {$$4,3,1,2$$}
9. {$$4,3,2,1$$}

In this example, I think that the chance of picking two derangements that are derangements of each other is $$P(A_4)=.5$$, since, for example, if 1 is picked, then there is a $$\frac{1}{2}$$ chance of picking either 5, 6, 8, or 9 from the eight remaining derangements, and I believe the same is found if any other derangement is picked first.

We can define $$P(A, n)=\frac{1}{n} \Sigma_{i=1}^n P(A_i)$$. What can we expect $$\lim_{n\rightarrow\infty}P(A,n)$$ to be? If we cut off $$n$$ at $$n=4$$, then we get $$P(A,4) = \frac{1}{4}(0+0+1+.5) = 0.375$$. Can we expect $$\lim_{n\rightarrow\infty}P(A,n)$$ to converge to zero, or can we expect $$\lim_{n\rightarrow\infty}P(A,n)>0$$? If a non-zero value of the limit exists, what is it, and how can it be found?

• There is no such thing as a uniform random natural number, so your assumption about random $n$ is nonsense. You can only do this if you assume $n\leq N$ and then take the limit as $N\to\infty,$ but then the result isn’t a probability, just a limit of probabilities. Dec 19, 2021 at 21:43
• @ThomasAndrews you are correct, and I reworded my question to reflect that. Dec 19, 2021 at 23:47
• Looking into latin rectangles with 3 rows may be useful for this, but I don’t know enough about them to give an answer Dec 20, 2021 at 2:51
• " I think that the chance of picking two derangements that are derangements of each other is 1/2" What if you pick 2) you can only pick as second derangement either 5) or 7) so its not quite uniform. Sage tells me that, if I understood correctly, $P(A_4)=0.33$ Feb 12, 2022 at 10:35
• In the large $n$ limit, it doesn’t matter; but for finite $n$ you need to specify whether the two randomly chosen derangements can be the same or not (i.e., whether you’re choosing two with or without replacement). Feb 14, 2022 at 7:54

Let $$D_n \subset S_n$$ be the set of derangements. It is well-known that $$|D_n| / |S_n| \to e^{-1}$$ as $$n \to \infty$$. In fact $$|D_n|$$ is exactly equal to $$n!/e$$ rounded to the nearest integer.
You ask about the probability that two elements $$x, y \in D_n$$ are derangements of each other, or equivalently $$xy^{-1} \in D_n$$. Now because $$xy^{-1}$$ has no apparent special properties one expects it to be roughly the same thing as a uniformly random element of $$S_n$$, and therefore one expects $$P(xy^{-1} \in D_n) \to e^{-1}$$.
This guess can be verified using some nontrivial tools from representation theory. In terms of convolution, we are trying to estimate $$\langle 1_{D_n} * 1_{D_n}, 1_{D_n}\rangle$$, and this can be expressed in terms of characters: $$\langle 1_{D_n} * 1_{D_n}, 1_{D_n} \rangle = \sum_\chi \chi(1)^{-1} \langle \chi, 1_{D_n} \rangle^3.$$ The main term, arising from the trivial character, is $$\langle 1, 1_{D_n} \rangle^3 = (|D_n| / |S_n|)^3$$. The term arising from the sign character is $$\pm (n-1)^3 / n!^3$$, which is tiny, and the sum of everything else is small because the degree of every other character is at least $$n-1$$ and $$\sum_{\chi \neq 1, \mathrm{sgn}} \chi(1)^{-1} |\langle \chi, 1_{D_n}\rangle|^3 \leq (n-1)^{-1} \big(\sum_\chi |\langle \chi, 1_{D_n} \rangle|^2 \big)^{3/2} = (n-1)^{-1} (|D_n| / |S_n|)^{3/2}.$$ This is also related to quasirandomness.