Understanding derangements

285 Views Asked by At

From the inclusion-exclusion principle we get that out of $N$ objects with one label each, there is a probability of $$\sum_{k=1}^N (-1)^{k+1}\frac{1}{k!}$$ that a random assignment of the $N$ labels to the $N$ objects will results in at least one match.

Would the derangement (the probability that there is no match) be $$1-\sum_{k=1}^N (-1)^{k+1}\frac{1}{k!}$$ then?

2

There are 2 best solutions below

0
On BEST ANSWER

Yes, because the two events are complementary. There's really nothing else to say.

0
On

As stated in another answer, this is correct because the event set $\overline{E}$ defined such that all the mappings in $\overline{E}$ are derangements of the original set of $n$ objects is the complement of the event set $E$ defined such that all the mappings in $E$ map at least one element from the set of $n$ objects to itself. But an interesting result of this equation can be discovered by expanding the sum:

$$1 - \displaystyle\sum_{k = 1}^n(-1)^{k -1} \dfrac{1}{k!} = 1 - \dfrac{1}{1!} + \dfrac{1}{2!} - \cdots + (-1)^n \dfrac{1}{n!}$$

You may now notice that this resembles the Maclaurin series of $e^x$ when $x = -1$. So,

$$\displaystyle\lim_{n \rightarrow \infty}1 - \displaystyle\sum_{k = 1}^n(-1)^{k -1} \dfrac{1!}{k!} = \dfrac{1}{e}$$