Two sets A, B of size n. Each element selects one element of the other set. Probability of no mutual selection? Came up in a challenge list of probability interview Q's.
You have two sets A, B of size n each. Each member in set A designates a member in B at random. Each member in set B designates a member in A at random. What is the probability of no mutual designation?
Where I got to:
Use an n-tuple (k_1, k_2, ...k_n) to represent how many members of A are designated to the i-th member of B.
I get that each tuple is created by (n!)/[(k_1!)(k_2!)...(k_n!)] designations of A. Or more simply ${n \choose k_1 ... k_n}$
For each n-tuple, I also get there are $\Pi_k (n-k_i)^{k_i}$ to satisfy the no mutual requirement from B's designations.
Putting that altogether I get:
$\Sigma_{k_1 + k_2 .... k_n = n}  {n \choose k_1 ... k_n} * \Pi_k (n-k_i)^{k_i}$
Which seems to be really close to multinomial expansion, but not quite.
Tried a few other methods, too. But they keep running into the issue that each tuple allocation (barring permuting the order) results in different number of combinations (ways to reach via A times ways to preserve no mutual from B).
 A: When I encounter problems like these, my instinct is always to:

*

*Use the method of moments to prove that the number of mutual selections (or whatever) converges to a Poisson random variable in distribution;

*Conclude that as $n \to \infty$, the probability of having no mutual selections goes to $e^{-\mu}$, where $\mu$ is the expected number of mutual selections (here, $1$).

If $\mathbf X$ is the number of mutual selections, we can show that for a constant $k$ and $n \ge k$, $\mathbb E[\binom{\mathbf X}{k}] = k! \binom nk^2 n^{-2k} \sim \frac1{k!}$, which is what we expect from a Poisson random variable with mean $1$. So that ticks off the first box.
(Why this expected value? Well, $\binom{\mathbf X}{k}$ counts the number of $k$-sets of mutual selections. There are $k! \binom nk^2$ ways to describe a potential such $k$-set in terms of which $A$-elements are matched with which $B$-elements, and each one is actually a $k$-set of mutual selections with probability $n^{-2k}$.)
In particular, $\mathbb E[X] = 1$, so $\Pr[\mathbf X = 0] \to e^{-1}$ as $n \to \infty$.
