7
$\begingroup$

We have a deck with $n$ cards enumerated $1,2,\ldots,n$. The deck is shuffled. What is the probability of exactly one card to remain on its original position? What is the limit as $n$ rises to infinity?

$$ \begin{array}{rcl} \{1\} & : & \dfrac 11 \\[6pt] \{12,21\} & : & \dfrac 02 \\[6pt] \{123,132,213,231,312,321\} & : & \dfrac 36 \\[6pt] & \vdots \end{array} $$

At $n = 100 0$ and $10 000$ trials:

$$ \begin{array}{rcl} \text{value of }n & & \text{probability} \\ \hline 1000 & & 0.3739 \\ 1001 & & 0.3689 \\ 1002 & & 0.3722 \\ 1003 & & 0.3638 \\ 1004 & & 0.3707 \\ 1005 & & 0.3664 \\ 1006 & & 0.3616 \\ 1007 & & 0.3728 \\ 1008 & & 0.3702 \\ 1009 & & 0.3801 \end{array} $$

At $n = 100 000$ and $10 000$ trials:

$\text{value of } n \quad \text{probability}$

$\quad 100000 \quad \quad 0.3659$

$\quad 100001 \quad \quad 0.3552$

$\quad 100002 \quad \quad 0.356$

$\quad 100003 \quad \quad 0.367$

$\quad 100004 \quad \quad 0.3738$

$\quad 100005 \quad \quad 0.3647$

$\quad 100006 \quad \quad 0.3654$

$\quad 100007 \quad \quad 0.3637$

$\quad 100008 \quad \quad 0.3718$

$\quad 100009 \quad \quad 0.3708$

Apparently, probability approaches $0.36-0.38$, but how can one derive it analytically?

$\endgroup$
15
$\begingroup$

To find the number of "good" permutations fix one card and derange the rest $(n-1)$ cards. This can be done in $!n$ ways. ($!n$ is the number of derangements of $n$ objects). Then the number of "good" permutations is $n\cdot !(n-1)$. Hence we have:

$$\lim_{n \to \infty} p_n = \lim_{n \to \infty} \frac{n\cdot !(n-1)}{n!} = \lim_{n \to \infty} \frac{!(n-1)}{(n-1)!} = e^{-1}$$

The last limit can be seen in the link I added above.

$\endgroup$
  • $\begingroup$ Isn't this overcounting the cases where two or more cards are in their original position? $\endgroup$ – Taemyr Jan 25 '17 at 9:32
  • 2
    $\begingroup$ @Taemyr The term "derangement" means that the other n-1 cards have a position different from their original one. This is why it's $!(n-1)$, not $(n-1)!$. $\endgroup$ – Antitheos Jan 25 '17 at 11:08
11
$\begingroup$

By the inclusion-exclusion principle, in the symmetric group $S_n$ there are $$ n!\sum_{k=0}^{n}\frac{(-1)^k}{k!} $$ permutations without fixed points (see derangements). It follows that in the same group there are $$ n\cdot (n-1)!\sum_{k=0}^{n-1}\frac{(-1)^k}{k!} $$ elements with exactly one fixed point, and the limit probability is $\color{red}{\large\frac{1}{e}}$ in both cases.

$\endgroup$
  • $\begingroup$ Then the limit probability of at most one fixed point is $\frac{1}{e}+\frac{1}{e}=\frac{2}{e}$. And for two fixed points? $\endgroup$ – Jeppe Stig Nielsen Jan 24 '17 at 22:32
  • 1
    $\begingroup$ @JeppeStigNielsen: correct. The probability of having exactly two fixed points is given by $$\frac{1}{n!}\binom{n}{2}(n-2)!\sum_{k=0}^{n-2}\frac{(-1)^k}{k!}\to\color{red}{\frac{1}{2e}}$$ and the limit probability of having exactly $k$ fixed points is $\frac{1}{k! e}$. $\endgroup$ – Jack D'Aurizio Jan 24 '17 at 22:35
  • $\begingroup$ Yes, I was just realizing that. Thanks. $\endgroup$ – Jeppe Stig Nielsen Jan 24 '17 at 22:41
  • 4
    $\begingroup$ In other words, as $n \to \infty$ the number of fixed points of a random permutation of $n$ elements converges in distribution to a Poisson(1) random variable. $\endgroup$ – Michael Lugo Jan 25 '17 at 0:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.