2022/10/31 by Peter Kagey, Kagey, Peter
Computer Science · Mathematics · #05A05 #Advanced Combinatorial Mathematics #Advanced Mathematical Identities #Bayesian Methods and Mixture Models #Combinatorics (math.CO) #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2210.17021
openalex publication_date 2022/10/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We discuss efficient methods for unranking derangements and ménage permutations. That is, we will provide an algorithm to efficiently extract the k-th earliest such permutation under the lexicographic ordering. We will show that this problem can be reduced to the problem of computing the number of restricted permutations with a given prefix, and then we will use rook theory to solve this counting problem. This has applications to combinatorics, probability, statistics, and modeling.