Enumerating separable derangements

Abstract

We give a polynomial-time algorithm to compute the number $b_n$ of separable derangements of $[n]$. This algorithm is based on a generating function technique which tracks permutations along with their occupied diagonals, where each permutation is counted once for every such diagonal. We provide bounds for the proportion of separable permutations which are derangements, show that $b_n$ and the large Schröder numbers have the same exponential growth constant $(3+2\sqrt{2})$, and use the first 3000 terms to conjecture more explicit asymptotic behavior. This partially answers several questions about separable derangements recently posed by Vatter.