The Distribution of the Combined Length of Spanned Cycles in a Random Permutation

For a random permutation π on {1,2,…,n} for fixed n, and for M⊆{1,2,…,n}, we analyse the distribution of the combined length L=L(π,M) of all cycles of π that contain at least one element of M. We give a simple, explicit formula for the probability of every possible value for L (backed by three proofs of distinct flavours), as well as closed-form formulae for its expectation and variance, showing that less than 1/(|M|+1) of the elements 1,…,n are expected to be contained in cycles of π that are disjoint from M, with low probability for a large deviation from this fraction. We furthermore give a simple explicit formula for all rising-factorial moments of L. These results are applicable to the study of manipulation in matching markets.