[Math Talk #18] Secret of Shuffling - Derangements

mathsolver (53)in #math • 6 years ago (edited)

[1]

0. What is a Derangement?

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 $n$ items (a finite set), each labeled as

$\left\{ 1, 2, ..., n \right\}$

So, put another way, a derangement of $n$ objects is a permutation of them without fixed points. The number of derangements of $n$ obejcts is usually written as $D_n$ .

For example, $D_1 = 0$ , since singleton set can not have any derangements. Also $D_2 = 1$ , because only derangement is assigning

$1 \mapsto 2,\ 2 \mapsto 1$

Let's look at one more example $D_3$ . 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 $n!$ different permutations of $n$ distinct objects, how many leave no object in its original place?

The answer to the question will provide a general formula for $D_n$ as well as

$p_n = \frac{D_n}{n!}$

the probability that a permutation of $n$ objects is a derangement.

1. Old but Gold Recurrence Relation

Viewing $D_1, D_2,D_3, ..., D_n,...$ as a sequence $\left\{ D_n \right\}$ , let's find a recurrence relation for $D_n$ . Since we already know the value of $D_1$ and $D_2$ , let's focus on the values of $D_n$ for $n \geq 3$ .

If a permutation

$\sigma: \left\{ 1, 2, ..., n \right\} \rightarrow \left\{ 1, 2, ..., n \right\}$

is a derangement, then it must be that $\sigma(1) \neq 1$ , which leaves $n-1$ possibilities for it. Among those, choose

$\sigma(1) = k (> 1)$

Now there are two possibilities.

1. If $\sigma(k) = 1$ , this is nothing but derangement of

$\left\{ 2, 3, ...,k-1, k+1,...n \right\} = \left\{ 1, 2, ..., n \right\} \setminus \left\{1,k \right\}$
and there are exactly $D_{n-2}$ of these.

2. If $\sigma(k) \neq 1$ , this is nothing but derangement of

$\left\{ 2, 3, ..., n \right\}$

$\left\{ 1, 2, ..., k-1, k+1, ..., n \right\}$

with a restriction $\sigma(k) \neq 1$ . The situation is totally equivalent to derangement of

$\left\{ 2, 3, ..., n \right\}$

if $1$ is viewed as $k$ ; so there are exactly $D_{n-1}$ of these.

Since our choice of $k$ was arbitrary, summing all those cases gives

$D_n = (n-1)(D_{n-1} + D_{n-2})\ (n \geq 3)$

How do we solve this?

Clever trick is to divide both sides by $n!$ so that

$\begin{align*} \frac{D_n}{n!} &= \frac{(n-1)D_{n-1}}{n!} + \frac{(n-1)D_{n-2}}{n!} \\ &= \frac{D_{n-1}}{(n-1)!} \left(1- \frac{1}{n} \right ) + \frac{D_{n-2}}{(n-2)!} \cdot \frac{1}{n}\\ \iff p_n &= \left(1- \frac{1}{n} \right ) p_{n-1} + \frac{1}{n} \cdot p_{n-2} \\ \iff (p_n &- p_{n-1}) = -\frac{1}{n} (p_{n-1} - p_{n-2}) \end{align*}$

Defining $q_n = p_n - p_{n-1}$ gives

$\begin{align*} q_n &= \left( -\frac{1}{n} \right ) \times \left( -\frac{1}{n-1} \right ) \times ... \times \left( -\frac{1}{1} \right ) \\ &= (-1)^{n} \frac{1}{n!} \end{align*}$

so that

$p_n = q_1 + ... + q_n = \sum_{i=1}^{n} (-1)^{i}\frac{1}{i!}$

with

$D_n = n! \left( \sum_{i=1}^{n} (-1)^{i}\frac{1}{i!} \right)$

2. The other way around

[2]

We've established the formula for derangement, but there is a more intuitive way of relating the total number of permutations $n!$ with $D_n$ .

We can count the total $n!$ ways by partitioning the ways into $n+1$ disjoint subsets,

$T_0,T_1,T_2,...,T_n$

where $T_r$ is the set of permutations in which there are exactly $n-r$ fixed points. If there are $n-r$ fixed points, we first choose $n-r$ fixed points among $n$ , and arrange leftovers ( $r$ elements) to have no fixed points. This gives

$|S_r| = \binom{n}{n-r}D_r = \binom{n}{r}D_r$

so that

$n! = \sum_{r=0}^{n} \binom{n}{r} D_r$

This simple looking relationship is indeed very useful, as we will use in further sections.

3. Expected Number of Fixed points

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 $\left\{ 1, 2, ..., n \right\}$ with a random permutation of itself. Define a random variable $X$ as the number of fixed points in single experiment. Then clearly, $X$ can have values

$0, 1, 2, ..., n$

So the expectation is nothing but

$\mathbb{E}[X] = \sum_{r=0}^{n} r\mathbb{P}(X = r)$

In the previous Section, we already obtained the formula for $\mathbb{P}(X = r)$ , which is

$\mathbb{P}(X = r) = \frac{|T_{n-r}|}{n!} = \frac{\binom{n}{n-r} D_{n-r}}{n!}$

Now, straightforward calculation gives

$\begin{align*} \mathbb{E}[X] &= \sum_{r=0}^{n} r \frac{\binom{n}{n-r} D_{n-r}}{n!} \\ &= \sum_{s=0}^{n} (n-s) \frac{\binom{n}{s}D_s}{n!}\ (\because s = n-r) \\ &= \sum_{s=0}^{n-1} \frac{D_s}{s!(n-s-1)!}\ (\because n-n=0)\\ &= \frac{1}{(n-1)!}\sum_{s=0}^{n-1} \binom{n-1}{s}D_s \end{align*}$

Since

$\sum_{s=0}^{n-1} \binom{n-1}{s}D_s = (n-1)!$

by our previous result in Section 3, we get

$\mathbb{E}[X] = 1$

regardless of $n$ .

How should we interpret this weird result? Many of us tend to think the expected number of fixed points will grow as $n$ increases. However, the probability of making an element $i$ as a fixed point is

inversely proportional to $n$

This will help you understand what's going on more clearly. Consider a random variable $X_i$ such that $X_i = 1$ if $i$ is a fixed point, and 0 otherwise. Then the expectation of number of fixed points is

$\sum_{i=1}^{n} \mathbb{P}(X_i = 1) = \frac{1}{n} \times n =1$

so that $1/n, n$ cancel out making the expectation constant; 1.

4. Asymptotic Property of derangement

[3]
Finally, one can ask that

What is the asymptotic behavior of $p_n$ as $n$ gets large?

This is nothing but asking the limit

$p=\lim_{n \rightarrow \infty} p_n = \sum_{i=0}^{\infty}(-1)^i \frac{1}{i!}$

one can easily show that the limit actually exists, and surprisingly, using the well known fact

$e^{x} = \sum_{i=0}^{\infty} \frac{x^i}{i!}\ (\text{for all } x \in \mathbb{R})$

gives $p = \frac{1}{e}$ .

Also one can ask that

What is the asymptotic behavior of $\mathbb{P}(X = r)$ as $n$ gets large?

Recall that we defined random variable $X$ as number of fixed points in single random permutation? Using the definition in Section 2 gives

$\mathbb{P}(X = r) = \frac{\binom{n}{n-r}D_{n-r}}{n!} = \frac{1}{r!} \cdot \frac{D_{n-r}}{(n-r)!}$

We already proved that $\frac{D_{n-r}}{(n-r)!} \rightarrow \frac{1}{e}$ , so that

$\mathbb{P}_n(X = r) \rightarrow \frac{e^{-1}}{r!}$

5. Computer Simulation

5-1. Expected number of fixed point revisited

Here is the MATLAB simulation for accumulated expectation of number of fixed points for various $n$ . As the number of simulation grows, you can see the accumulated expectation approaches to unity, regardless of $n$ .

5-2. Asymptotic property of Derangement revisited

Now here is the MATLAB simulation for $p_n$ the probability of having derangement in single permutation.

You can see it clearly converges to $1/e$ , oscillating in small region centered $1/e$ .

6. Conclusion

Number of derangement of $n$ items is equal to

$n!\sum_{r=0}^{n} \frac{(-1)^r}{r!}$
The expectated number of fixed points in single random permutation is 1, regardless of $n$ .
The probability of having derangement converges to $p_n \rightarrow 1/e$ .

7. Citations

[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.

#mathematics #science #steemstem #steemiteducation

6 years ago in #math by mathsolver (53)

$4.93

Sort:

Trending

[-]

steemitboard (66) 6 years ago

Congratulations @mathsolver! You have completed the following achievement on Steemit and have been rewarded with new badge(s) :

Award for the number of comments

_{Click on the badge to view your Board of Honor.}
_{If you no longer want to receive notifications, reply to this comment with the word STOP}

You can upvote this notification to help all Steemit users. Learn why here!

$0.00

[-]

steemstem (73) 6 years ago

This post has been voted on by the steemstem curation team and voting trail.

There is more to SteemSTEM than just writing posts, check here for some more tips on being a community member. You can also join our discord here to get to know the rest of the community!

$0.00

[-]

utopian-io (71) 6 years ago

Hi @mathsolver!

Your post was upvoted by utopian.io in cooperation with steemstem - supporting knowledge, innovation and technological advancement on the Steem Blockchain.

Contribute to Open Source with utopian.io

Learn how to contribute on our website and join the new open source economy.

Want to chat? Join the Utopian Community on Discord https://discord.gg/h52nFrV

$0.00