# What is the conceptual misunderstanding in the hat-check problem (derangements)?

The hat-check problem goes something like this: there are N letters that correspond to N envelopes. They get put in randomly. What is the probability that none of them are in the correct envelope (and also, the probability that at least one is in the correct envelope)?

I understand that the approach is the derangements approach, but I initially tried it in the following way and don't fully understand the flaw on why you can't calculate P(all letters are in wrong envelopes) directly.

My approach was the following. The first letter has probability N-1/N of being misplaced. Then, the second envelope has probability N-2/N-1. This continues until everything cancels, leaving P(all letters are in wrong envelopes) = 1/N and hence P(at least one letter is correct) = 1 - 1/N. However, this simply isn't right. I understand the formula and derivation for derangements, but what is conceptually wrong with this approach?

My thoughts are that the error could come from only considering one particular sequence, but I'm really not too sure.

Consider this Image , where the upper line has the letters $$l_1,l2,\cdots,l_n$$ & the lower line has the Envelopes $$E_1,E_2,\cdots,E_n$$ , where I have taken Example $$n=5$$.

The Grey Dotted lines will Correctly match the letters & Envelopes , hence these are not allowed.

Here , $$l_1$$ can go to $$E_2,\cdots,E_n$$ , $$n-1$$ ways which you gave Correctly.
Consider the Case when $$l_1$$ goes to $$E_3,E_4,E_5$$ (Black lines) , then $$l_2$$ can not go there & it can not go to $$E_2$$ , hence it has $$n-2=3$$ ways which you gave Correctly.

The hitch is that $$l_1$$ might go to $$E_2$$ (Purple line) , then $$l_2$$ can go to $$E_1,E_3,E_4,E_5$$ , hence it has $$n-1=4$$ ways ! This is where the Simple Calculation will go wrong.

Like-wise , consider $$l_3$$ which can not go to $$E_3$$ : If $$l_1$$ & $$l_2$$ had avoided $$E_3$$ , then $$l_3$$ has $$n-3$$ ways.
If $$l_1$$ had gone to $$E_3$$ & $$l_2$$ had gone else-where , then $$l_3$$ has $$n-2$$ ways.
If $$l_2$$ had gone to $$E_3$$ & $$l_1$$ had gone else-where , then $$l_3$$ has $$n-2$$ ways.
It is making the Simple Calculation more & more Cumber-Some !

Consider $$l_n$$ which can not go to $$E_n$$ : If some other letter has used up that Envelope , then $$l_n$$ has $$1$$ Envelop to use , hence $$1$$ way.
If no other Envelop had used up that Envelop , then $$l_n$$ has $$E_n$$ , which makes the whole thing invalid.
It is making the Simple Calculation totally wrong !

Thus the Simple Calculation you gave is not going to work.
We have to use the Correct Derangement Calculation.

[[ User "0XLR" had made a Correct Comment , I am Elucidating & Elaborating in my way ]]