Separable permutations are a well-studied family of permutations that can be built up recursively by combining smaller pieces, and derangements are permutations where no element stays in its original position. The paper focuses on counting objects that are both: separable derangements. Despite how natural this combination sounds, computing how many such objects exist for a given size turned out to be a nontrivial problem that had been posed as an open question.
The main contribution is an efficient algorithm, running in polynomial time, that computes the number of separable derangements of size n. The key technical idea involves a generating function that keeps track of permutations alongside a geometric feature called their "occupied diagonals." This is a clever bookkeeping device that allows the authors to impose the derangement condition (no fixed points) within the recursive structure that defines separable permutations, something that is not straightforward to do directly.
Beyond the algorithm, the paper establishes several results about the growth and proportion of these objects. The authors show that the count of separable derangements grows at the same exponential rate as the large Schroder numbers, a well-known sequence in combinatorics, with the growth constant being 3 plus 2 times the square root of 2. They also find that a positive fraction of all separable permutations are derangements, and using the first 3000 computed terms, they propose a more precise asymptotic formula. These results answer several open questions that had been recently posed in the literature.