Conditional Probability of Derangements and Fixed Points

Abstract

The probability that a random permutation in $S_n$ is a derangement is well known to be $\sum _{j=0}^n(-1{)}^j\frac{1}{j!}$. In this paper, we consider the conditional probability that the $(k+1{)}^{st}$ point is fixed, given there are no fixed points in the first $k$ points. We prove that when $n\ne 3$ and $k\ne 1$, this probability is a decreasing function of both $k$ and $n$. Furthermore, it is proved that this conditional probability is well approximated by $\frac{1}{n}-\frac{k}{n^2(n-1)}$. Similar results are also obtained about the more general conditional probability that the $(k+1{)}^{st}$ point is fixed, given that there are exactly $d$ fixed points in the first $k$ points.

16 pages, 2 figures. To be published in Transactions on Combinatorics