Is there a "closed form expression" for below problem ?
Problem :
"N" guests gave their raincoats and their umbrellas to the doorman at the entrance of the “Marlinspike” mansion in order to attend the party. At the end of the night, the doorman was completely plastered. So, he gave the leaving guests a random raincoat and a random umbrella, in a way that each person got a pair of raincoat and umbrella in a uniformly random manner.
Questions :
a. What is the probability that nobody gets back his own raincoat and his umbrella?
b. What is the probability that everybody gets at least his own raincoat or his own umbrella?
recall orginal derangement (1 variable):
$$ |\bar{A_1},\bar{A_2},...,\bar{A_n}|=|S|-\sum_{i=1}^n |A_i|+\sum_{i=1 j=1}^n |A_iA_j|-...=n!-\begin{pmatrix}n\\1\end{pmatrix}(n-1)!+...+(-1)\begin{pmatrix}n\\n\end{pmatrix}(n-n)! $$ $$ D_n=n!(1-\frac{1}{1!}+\frac{1}{2!}-...+\frac{(-1)^n}{n!})=n!(\sum_{i=0}^n\frac{(-1)^i}{i!})$$ $$ P(D_n)=\sum_{i=0}^n\frac{(-1)^i}{i!}$$
Answer :
a) derangement with 2 independant variable:
$$ |(\overline{U_1\cup R_1}),(\overline{U_2\cup R_2}),...,(\overline{U_n\cup R_n})|=|(\overline{U_1}\cap \overline{R_1}),(\overline{U_2}\cap \overline{R_2}),...,(\overline{U_n}\cap \overline{R_n})|=$$ $$|(\overline{U_1},\overline{U_2},...,\overline{U_n})\cap(\overline{R_1},\overline{R_2},...,\overline{R_n})|=$$ $$(D_n)^2=(n!)^2\left[1-\frac{1}{1!}+\frac{1}{2!}-...+\frac{(-1)^n}{n!}\right]^2$$ $$P(D_n^2)=\left(\sum_{i=0}^n\frac{(-1)^i}{i!}\right)^2$$
b) derangement with 2 dependant variable:
$$|(U_1\cup R_1),(U_2\cup R_2),...,(U_n\cup R_n)|=$$ $$\sum_{i=0}^n\begin{pmatrix}n\\i\end{pmatrix}\left[\sum_{k=0}^{n-i}\begin{pmatrix}{n-i}\\k\end{pmatrix}.D_{(n-i-k)}.\begin{pmatrix}{n-i}\\{n-i-k}\end{pmatrix}.D_{(k)}\right]$$ so $$P((U_1\cup R_1),(U_2\cup R_2),...,(U_n\cup R_n))=\frac{\sum_{i=0}^n\begin{pmatrix}n\\i\end{pmatrix}\left[\sum_{k=0}^{n-i}\begin{pmatrix}{n-i}\\k\end{pmatrix}.D_{(n-i-k)}.\begin{pmatrix}{n-i}\\{n-i-k}\end{pmatrix}.D_{(k)}\right]}{n!n!}$$ $$=\frac{\sum_{i=0}^n\frac{n!}{i!(n-i)!}\left[\sum_{k=0}^{n-i} \left(\frac{(n-i)!}{k!(n-i-k)!} \right) \left( (n-i-k)! \sum_{f=0}^{n-i-k}\frac{(-1)^f}{f!} \right) \left(\frac{(n-i)!}{k!(n-i-k)!} \right) \left( (k)! \sum_{l=0}^{k}\frac{(-1)^l}{l!} \right) \right]}{n!n!}$$ $$=\frac{\sum_{i=0}^n\frac{n!}{i!(n-i)!}\left[\sum_{k=0}^{n-i} \left(\frac{((n-i)!)^2}{k!(n-i-k)!} \right) \left( \sum_{f=0}^{n-i-k}\frac{(-1)^f}{f!} \right) \left( \sum_{l=0}^{k}\frac{(-1)^l}{l!} \right) \right]}{n!n!}$$
I didn't have time to write a detailed answer yesterday.
Let us say that exactly $k$ people get their own raincoats, where $0\leq k\leq n$. There are $\binom nk$ ways to choose which $k$ people get their own raincoats, and since the other $n-k$ people do not get their own raincoats, there are $D_{n-k}$ ways to distribute the remaining raincoats.
To fulfill the condition, each of the $n-k$ people who did not receive his own raincoat must get his own umbrella, leaving $k$ umbrellas to distribute. But these are precisely the umbrellas of the people who got their own raincoat. It doesn't matter how we distribute these umbrellas, since everyone has already received his own raincoat or his own umbrella. We may distribute the umbrellas in $k!$ ways.
This gives $$ \sum_{k=0}^n\binom nkD_{n-k}k!=\sum_{k=0}^n\frac{n!D_{n-k}}{(n-k)!}=n!\sum_{k=0}^n\frac{D_k}{k!} $$
We may test this when $n=3$.
$$ \begin{align} n!\sum_{k=0}^n\frac{D_k}{k!} &=3!\sum_{k=0}^3\frac{D_k}{k!}\\ &=6\left(\frac{D_0}{0!}+\frac{D_1}{1!}+\frac{D_2}{2!}+\frac{D_3}{3!}\right)\\ &=6\left(\frac11+\frac01+\frac12+\frac26\right)\\ &=6\left(\frac{6+0+3+2}{6}\right)\\ &=11 \end{align} $$ in agreement with the picture you posted.
To get the probability we must divide by $(n!)^2$ giving the simple expression $$\frac1{n!}\sum_{k=0}^n\frac{D_k}{k!}$$ or if we use the common notation $!k$ in place of $D_k$, $$\frac1{n!}\sum_{k=0}^n\frac{!k}{k!}$$