(Feller Volume 1, P.112, Q.20) There are two similar decks of $N$ distinct cards. Out of the $2N$ cards $N$ are chosen at random, and only these $N$ are matched against the target deck. Find the probability of no match.
Answer: $\sum_{k=0}^N \frac{{N \choose k}2^k(2N-k)!(-1)^k}{(2N)!}$.
My attempt: We can arrange the target deck in a natural order: $1, 2, 3, … , N$. We have ${2N \choose N}$ ways to choose $N$ cards. Let $A_k$ be the event that the card number $k$ is matched. Then, the probability of no match is $1- P(A_1 \cup A_2 \cup \cdot\cdot\cdot \cup A_N)$. Then, I can use the inclusion and exclusion method.
But, I am not sure how to compute $P(A_i), P(A_i \cap A_j),…$, and I don't know if this is the right approach. Any help would be appreciated.
Best Answer
$$P\left(A_{1}\cap\cdots\cap A_{k}\right)=P\left(A_{1}\right)P\left(A_{2}\mid A_{1}\right)\cdots P\left(A_{k}\mid A_{1}\cap\cdots\cap A_{k-1}\right)=$$$$\frac{1}{2N-1}\frac{1}{2N-3}\cdots\frac{1}{2N-2k+1}=\frac{2^{k}N!\left(2N-2k\right)!}{\left(2N\right)!\left(N-k\right)!}$$