Based on a joke going around in Video Game randomizers, where items that are appearing to be "not randomized" are thought to be broken, I was interested in the probabilities related to this.
To simplify, we have n items, which are randomized to appear in n positions.
This can be considered to be similar to be having a bag of n tokens, numbered 1 to n, and we draw them sequentially, so that in a bag of 3, a draw of 3-2-1 is counted as a draw in sequential order, as 2 is drawn in position 2.
Now, the probability of drawing them all in order is simple, $\frac{1}{n!}$. But what is the probability of none of them being in order? (Because, obviously, none of them being in their original order is "truly" random.....) Based on a question and comment here it seems that Rencontres numbers fit my empirical test at low numbers, where
| n | No sequential draw occurrences | Probability |
|---|---|---|
| 3 | 2 | 2/6 = 1/3 |
| 4 | 9 | 9/24 = 3/8 |
| 5 | 44 | 44/120 = 11/30 |
So am I correct in saying that we can use the formula for Rencontres numbers here, which is
$$D_{n,0} = \left\lceil\frac{n!}{e}\right\rfloor$$
?
Which interestingly enough, without looking too hard on expanding that formula, seems to tend to around 0.3678 as n gets bigger.