The proportion of permutations fixing a $k$-set

Abstract

Denote by $p(k)$ the limit, as $n\to \infty$, of the probability that a random permutation on a set of size $n$ has an invariant set of size $k$. We give an asymptotic formula for $p(k)$, showing that it is asymptotically $f(\{{\log }_{2}k\})k^{-\hat{I}´}(\log k{)}^{-3/2}$ where $\hat{I}´=1-\frac{1+\log \log 2}{\log 2}\approx 0.086$ and $f$ is a smooth, positive, function on $\mathbb{R}/\mathbb{Z}$, which we will describe explicitly. The function $f$ satisfies $\frac{\max f}{\min f}<1+2\times 10^{-7}$ and we conjecture that it is not constant. Estimating $p(k)$ is a model for the more well-known question which asks for an estimation of $M(n)$, the number of distinct elements in the $n$-by-$n$ multiplication table. By elaborating on the techniques in this paper, we will give an asymptotic for $M(n)$ in forthcoming work.

116 pages