What’s the probability for this problem?

Question

in class we were working on a question regarding our seating plan. The question was: we are a class of 32 students sitting in pairs of 2. What is the probability of one or more pairs existing in an original seating plan and after shuffling all students around? I made a small simulation in php that gives me an approximation of 40.3% but I don’t know how to calculate it. If anybody is interested in the simulation and wants to look for an error there please say so and I’ll add it later

Answer 1

Trying an inductive proof assume we have 2n people and let $P_n$ be the number of distinct ways of pairing 2n people into n pairs

$P_1=1$ and $P_2=3$ are trivial

Now we can setup induction

Label the 2n people and pick person-1 and any other person for our first pair and remove them which leaves us with 2(n-1) people.

This gives $$ P_n=(2n-1)P_{n-1} \\ \ \\ P_n=(2n-1)(2n-3)...(3)(1)=\frac{(2n)!}{2^n(n!)} $$

Note: We can continue the formula for $P_0=1$

Now to solve the question lets take the initial permutation as {(1,2)(3,4)...(31,32)}

We can fix (1,2) which gives us $P_{15}$ pairs and similarly for the other 16 pairs

Now we need to deal with overcounting since we can fix multiple pairs

Using routine Inclusion Exclusion

$$ \begin{align}S&=16P_{15}-120P_{14}...+16P_1=^{16}C_1P_{15}-^{16}C_2P_{14}...+^{16}C_{15}P_1-^{16}C_{16}P_0\\ &=P_{16}-\sum_{r=0}^{16} {}^{16}C_rP_r(-1)^r \\ \ \\ &P(S)=1-\frac{\sum_{r=0}^{16} {}^{16}C_rP_r(-1)^r}{P_{16}}\approx 0.403 \end{align} $$

This answer also agrees with your sim

Huge thanks to @Robert Murray for pointing out a mistake in the first answer

Answer 2

I don't think RandomGuy's answer can be simplified.

An approximation for large $n$, where $n$ is the number of pairs and $m=2n$ the number of persons:

We can expect that the events $E_i \equiv$ "the pair $i$ survived", are asymptotically independent. Hence

$$\begin{align} p&= 1- P(E^c_1 \wedge E^c_2 \cdots E^c_n)\\ & \approx 1 - \prod_{i=1}^nP(E_i^c) \\ & = 1 - \left(1- \frac{1}{m-1}\right)^n \tag 1\\ \end{align} $$

For $n=32$ this gives $p \approx 0.40823$

As $n \to \infty$:

$$\begin{align} p& \approx 1 - e^{-n/(m-1)} \\ & \approx 1 - e^{-1/2} \\ & \approx 0.39347 \tag 2\\ \end{align} $$