Re-arranging Items

Probability Level 2

Line up $n \geq 2$ items in a row on a table. Now shuffle the items around and then re-arrange them in a row again. Let $P_n$ be the probability that there is no item in the same position as it was before it was shuffled. That is, all items were moved to a different position (for example, this would occur if all items were cycled one position to the right). Then,

$\underset{n\to \infty }{\text{lim}} P_n = \frac{a}{e^b}$

for positive integers $a,b$ . Submit $a+b$ .

Note: We assume that, after shuffling, every permutation of the items is equally likely.

The answer is 2.

1 solution

Arjen Vreugdenhil
Dec 21, 2017

The number of arrangements of $n$ elements is $n!$ . The number of derangements is $!n = n!\sum_{k=0}^n \frac{(-1)^k}{k!} \approx n!\sum_{k=0}^\infty \frac{(-1)^k}{k!} = n!e^{-1}.$ The probability that an arrangement is in fact a derangement is $\frac{!n}{n!} \approx \frac{n!e^{-1}}{n!} = \frac 1{e^1}.$ This approximation improves as $n$ increases. It is clear that $a = b = 1$ , so the answer is $1 + 1 = \boxed{2}$ .

Re-arranging Items

The answer is 2.

1 solution

0 pending reports