Probability of Derangement

Derangement is a permutation without a fixed point.

Derangement - Wikipedia, the free encyclopedia

The probability that $\displaystyle n$ elements are deranged is given by $\displaystyle \sum_{k=2}^n \frac{(-1)^k}{k!}$. So the probability exhibits the following properties:

(1) When $\displaystyle n$ increases from an odd number to an even number (say, from 3 to 4), the probability increases. That is, when elements are shuffled, they get more likely to be deranged.

(2) When $\displaystyle n$ increases from an even number to an odd number (say, from 4 to 5), the probability decreases. That is, when elements are shuffled, they get more unlikely to be deranged.

(3) When $\displaystyle n$ is restricted to odd numbers, the probability is an increasing function of $\displaystyle n$.

(4) When $\displaystyle n$ is restricted to even numbers, the probability is a decreasing function of $\displaystyle n$.

I want, if any, "intuitive" explanations of these properties. Whether an explanation is "intuitive" is very subjective, so any ideas are welcome.

Thank you for viewing this question, and I'm looking forward to your posts.

Re: Probability of Derangement

Quote:

Originally Posted by

**k-misako** Derangement is a permutation without a fixed point.

Derangement - Wikipedia, the free encyclopedia
The probability that $\displaystyle n$ elements are deranged is given by $\displaystyle \sum_{k=2}^n \frac{(-1)^k}{k!}$. So the probability exhibits the following properties:

(1) When $\displaystyle n$ increases from an odd number to an even number (say, from 3 to 4), the probability increases. That is, when elements are shuffled, they get more likely to be deranged.

(2) When $\displaystyle n$ increases from an even number to an odd number (say, from 4 to 5), the probability decreases. That is, when elements are shuffled, they get more unlikely to be deranged.

(3) When $\displaystyle n$ is restricted to odd numbers, the probability is an increasing function of $\displaystyle n$.

(4) When $\displaystyle n$ is restricted to even numbers, the probability is a decreasing function of $\displaystyle n$.

I want, if any, "intuitive" explanations of these properties.

I don't think that there is an "intuitive" explanation. What you have noticed is a result of the sum of an alternating series.

When $\displaystyle n=7$ we have six terms of which three are negative and three are positive.

When $\displaystyle n=8$ we have seven terms of which three are negative and four are positive.

So the probability increases.

It occurs me that a line of an odd number of distinct objects has a middle point. Whereas, an even number does not.

If you look at the **inclusion/exclusion principle of counting** from which the derangement sum is derived then I think you will have a better understanding of the sum.

Re: Probability of Derangement

> I don't think that there is an "intuitive" explanation.

I see. Maybe it's a bad habit for me to ask for intuitive explanations so often.

> It occurs me that a line of an odd number of distinct objects has a middle point. Whereas, an even number does not.

This might be relevant to that dividing the objects into pairs and then swapping each in the pairs leads automatically to derangement when $\displaystyle n$ is even, but it doesn't when $\displaystyle n$ is odd.

Thank you very much for your post.