PreprintCC BY 4.0arXiv
Enumerating separable derangements
Abstract
We give a polynomial-time algorithm to compute the number bn 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 bn and the large Schröder numbers have the same exponential growth constant (3 + 2 √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.
Related
BibTeX
@misc{doughertybliss2026enumerating,
title = {{Enumerating separable derangements}},
author = {Robert Dougherty-Bliss and Alejandro B. Galván and Michaela A. Polley and David Shuster},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.27583},
eprint = {2608.27583},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.27583},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Enumerating separable derangements
AU - Robert Dougherty-Bliss
AU - Alejandro B. Galván
AU - Michaela A. Polley
AU - David Shuster
PY - 2026
DA - 2026/08/27
PB - arXiv
DO - 10.48550/arxiv.2608.27583
UR - https://arxiv.org/abs/2608.27583
AB - 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 √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.
ER -