In mathematics, permutation is an act of arranging all the members of a set into some sequence or order. A permutation which leaves no element fixed is called a derangement . In many cases, we deal with items (a finite set), each labeled as
So, put another way, a derangement of objects is a permutation of them without fixed points. The number of derangements of
obejcts is usually written as
.
For example, , since singleton set can not have any derangements. Also
, because only derangement is assigning
Let's look at one more example . There are total 2 derangements,
| Element | 1 | 2 | 3 |
|---|---|---|---|
| maps to | 2 | 3 | 1 |
| maps to | 3 | 1 | 2 |
In general, we need to ask the question:
Of the different permutations of
distinct objects, how many leave no object in its original place?
The answer to the question will provide a general formula for as well as
the probability that a permutation of objects is a derangement.
Viewing as a sequence
, let's find a recurrence relation for
. Since we already know the value of
and
, let's focus on the values of
for
.
If a permutation
is a derangement, then it must be that , which leaves
possibilities for it. Among those, choose
Now there are two possibilities.
1. If , this is nothing but derangement of
2. If , this is nothing but derangement of
to
with a restriction . The situation is totally equivalent to derangement of
to
if is viewed as
; so there are exactly
of these.
Since our choice of was arbitrary, summing all those cases gives
How do we solve this?
Clever trick is to divide both sides by so that
Defining gives
so that
with
[2]
We've established the formula for derangement, but there is a more intuitive way of relating the total number of permutations with
.
We can count the total ways by partitioning the ways into
disjoint subsets,
where is the set of permutations in which there are exactly
fixed points. If there are
fixed points, we first choose
fixed points among
, and arrange leftovers (
elements) to have no fixed points. This gives
so that
This simple looking relationship is indeed very useful, as we will use in further sections.
A rather paradoxical situation arise when we calculate the expeced number of fixed points. Suppose that we perform the experiment of matching the initial arrangement with a random permutation of itself. Define a random variable
as the number of fixed points in single experiment. Then clearly,
can have values
So the expectation is nothing but
In the previous Section, we already obtained the formula for , which is
Now, straightforward calculation gives
Since
by our previous result in Section 3, we get
regardless of .
How should we interpret this weird result? Many of us tend to think the expected number of fixed points will grow as increases. However, the probability of making an element
as a fixed point is
inversely proportional to
This will help you understand what's going on more clearly. Consider a random variable such that
if
is a fixed point, and 0 otherwise. Then the expectation of number of fixed points is
so that cancel out making the expectation constant; 1.
[3]
Finally, one can ask that
What is the asymptotic behavior of as
gets large?
This is nothing but asking the limit
one can easily show that the limit actually exists, and surprisingly, using the well known fact
gives .
Also one can ask that
What is the asymptotic behavior of as
gets large?
Recall that we defined random variable as number of fixed points in single random permutation? Using the definition in Section 2 gives
We already proved that , so that
Here is the MATLAB simulation for accumulated expectation of number of fixed points for various . As the number of simulation grows, you can see the accumulated expectation approaches to unity, regardless of
.
Now here is the MATLAB simulation for the probability of having derangement in single permutation.
You can see it clearly converges to , oscillating in small region centered
.
Number of derangement of items is equal to
The expectated number of fixed points in single random permutation is 1, regardless of .
The probability of having derangement converges to .
[1] Image Source Link, By RokerHRO - Own work, CC BY 3.0
[2] Julian Havil, Nonplussed! Mathematical Proof of Implausible Ideas. Chapter 5 page 53
[3] Julian Havil, Nonplussed! Mathematical Proof of Implausible Ideas. Chapter 5 page 56
MATLAB plots are self-made.
