Empirical application for probability of $h$-deranged permutations

32 Views Asked by At

Background

For $n \in \mathbb{N}$ distinct items, there are a total of $n!$ permutations of them. A derangement is a permutation in which not a single item is in its 'natural position'. The number of derangements of a collection of $n$ distinct items is given by:

$$!n \triangleq n! \sum_{k=0}^{n}\frac{(-1)^k}{k!}$$

Since the set of derangements is an equivalence class within the set of permutations, and $!0 = 0!$, we can believe $!n \leq n!$. Taking $\Omega$ to be the set of permutations, a $\sigma$-algebra $\Sigma$ on $\Omega$, and a probability measure $\mathcal{P}(X) \triangleq \frac{\mathcal{C}(X)}{\mathcal{C}(\Omega)}$ where $\mathcal{C}$ is a counting measure on $\Omega$, we have the probability space $(\Omega, \Sigma, \mathcal{P})$. With the counting functions mentioned above, the probability of randomly selecting a permutation can be given by:

$$Pr(\text{Derrangement};n) = \frac{!n}{n!} = \sum_{k=0}^{n}\frac{(-1)^k}{k!}$$

By fixing $n-h$ positions to remain in their natural position, leaving $h$ positions to be deranged, the number of $h$-deranged permutations can be given by:

$$\binom{n}{n-h}!h$$

Similar to before, the probability of an $h$-deranged permutation being selected is given by any of the following equal expressions:

$$\frac{\binom{n}{n-h}!h}{n!} = \frac{!h}{h!(n-h)!} = \binom{n}{n-h}\sum_{k=0}^{h}\frac{(-1)^k}{k!}$$

With these definitions and expressions we can find that the probability of the $0$-deranged permutation is $\frac{1}{n!}$, the probability of an $h$-deranged permutation with $h \neq 0$ is $1 - \frac{1}{n!}$, and the probability of an $h$-deranged permutation with $h \neq n$ is $1 - \sum_{k=0}^{h}\frac{(-1)^k}{k!}$.

Question

Does there exist an empirical application (scientific, economic, engineering, etc) for computing probabilities of $h$-deranged permutations?