To make the problem slightly more general, take two samples of size √n from a population of size n where n is large.

The probability of no overlap in the two samples is approximately 1/e.

That is, in the limit as n approaches infinity, the probability converges to 1/e.

For n = 1,000,000 the approximation is good to three figures.

This problem is reminiscent of the birthday problem, but it’s a little different because the samples are draw without replacement.

*** [1] The statement of the problem and solution are simple.

The proof is not as simple.

.