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

d i s p l a y s t y l e s u m l i m i t s_{j = 0}^{n} (- 1)^{j} f r a c 1 j!

. In this paper, we consider the conditional probability that the

(k + 1)^{s t}

point is fixed, given there are no fixed points in the first

k

points. We prove that when

n e q 3

and

k e q 1

, this probability is a decreasing function of both

k

and

n

. Furthermore, it is proved that this conditional probability is well approximated by

f r a c 1 n - f r a c k n^{2} (n - 1)

. Similar results are also obtained about the more general conditional probability that the

(k + 1)^{s t}

point is fixed, given that there are exactly

d

fixed points in the first

k

points.

This page was built for publication: Conditional Probability of Derangements and Fixed Points