Probability of no repeated pairs

Question

Suppose there is a class with 40 students. The students carry out an initial project in randomly assigned pairs. If the students carry out a second project, what is the probability that none of the randomly assigned pairs of the second project is the same as in the first project? In other words, there can be no repeated pairs in the two projects.

Can anyone provide an answer to this question by using a simulation in R and then by providing a formula?

Answer 1

Probability of person being in same pair second time round is 1/19 So probability of being in different pair is 18/19

So probability of everyone being in different pair is (18/19)^20

Answer 2

This is a straightforward application of the principle of inclusion and exclusion. There are $$\frac{40!}{2^{20}20!}$$ ways to choose $20$ pairs from $40$ students. The second time around we must exclude any pair that was chosen the first time. There are $20$ such pairs, and $$\frac{38!}{2^{19}19!}$$ ways to make $19$ other pairs, which gives $$\frac{40!}{2^{20}20!}-20\frac{38!}{2^{19}19!}$$ But now any pairing that repeats two pairs has been subtracted out twice, so we must add those back in, and so on. This gives $$\sum_{j=0}^{20}(-1)^j\binom{20}{j}\frac{(40-2j)!}{2^{20-j}(20-j)!}$$ admissible pairings. Doing the arithmetic, there are $191549525877429961604096$ admissible pairings out of $319830986772877770815625$ possible ones, which gives a probability of $$\frac{191549525877429961604096}{319830986772877770815625}\approx0.5989085917227133$$

If we generalize the problem to $n$ pairings out of $2n$ students, the same reasoning applies, and we find that as $n\to\infty$ the probability that there are no repeated pairs approaches $e^{-1/2}\approx0.6065306597126334$, so that we are already pretty close to the limit when $n=40.$

Answer 3

Here's a quick simulation in R to go with the answer from @saulspatz:

set.seed(1)

pairing <- function() {
  permutation <- sample.int(40)
  lapply(seq(1, 39, 2), function(x) sort(permutation[x:(x + 1)]))
}

repeated_pairing <- function() any(pairing() %in% pairing())

trials <- 1000
results <- replicate(trials, !repeated_pairing())
sum(results) / trials
#> [1] 0.6

plot(1:trials, cumsum(results) / 1:trials)

^{Created on 2019-11-24 by the reprex package (v0.3.0)}