Double derangement

combinatoricsderangementspermutations

Let $[n]$ be a set with $n$ elements. Two derangements of this set, $\sigma$ and $\psi$ satisfy the next condition.

  • $\forall i\in [n], \sigma(i)\neq \psi(i)$

This condition makes $\sigma$ also a derangement of $\psi$. A double derangement of $[n]$ is an (ordered) pair {$\sigma;\psi$} such that $\forall i\in[n], \sigma(i)\neq\psi(i)$. How many double derangements can there be?

I have been thinking about this problem since I learned about derangements. I tried to solve this problem by finding a recurrence formula and using inclusion–exclusion principle, but figured out that it is too complicated to solve by this method. Are there any better ideas to solve this problem?

Best Answer

I believe you are looking for https://oeis.org/A000186. The formula is given by

$a(n) = n!\sum_{k+j<=n} \dfrac{2^j}{j!}k!\binom{-3(k+1)}{n-k-j}$. I checked with the following code:

from itertools import permutations
import math

def diff(x,y):
    return [a-b for a,b in zip(x,y)]
def derangements(s):
    'All deranged permutations of the integers 0..n-1 inclusive'
    return [perm for perm in permutations(s) if all(x!=0 for x in diff(perm,s)) ]


def t(n):
    c = 0
    ders = derangements(range(n))
    for i in ders:
        for j in ders:
            if all(x!=0 for x in diff(i,j)):
                c+=1
    return c
for i in range(7):
    print(t(i))
Related Question