[Math] Probability that no student sits on the same seat at two different days

combinatoricsprobability

A certain class has 20 students, and meets on Mondays and Wednesdays in a classroom
with exactly 20 seats. In a certain week, everyone in the class attends both days. On
both days, the students choose their seats completely randomly (with one student per
seat). Find the probability that no one sits in the same seat on both days of that week. (Introduction to Probability, Blitzstein and Nwang, p.38)

  • Let $E$ be the event that no student is on the same seat, and $E^c$ that at least one student is on the same seat, so $P(E) = 1 – P(E^c)$.
  • Let $A_i$ be the event that the $i^{th}$ student is on the same seat.
  • $P(E^c) = P(\cup_{i=1}^{20} A_i)$
  • $P(A_i) = 1/n$; $P(A_i \cap A_j) = 1/(n(n-1))$; $P(\cap_{i=1}^{t \leq 20} A_i) = 1/(\binom{n}{i}i!)$

Hence, $P(E^c) = \sum_{i=1}^{20} \binom{n}{i} * \frac{1}{\binom{n}{i}i!} * (-1)^{i+1} = \sum_{i=1}^{20} 1/i! (-1)^{i+1} = 0.632$, and so we get $P(E) = 0.368$

Is there a more straightforward way to arrive at the same answer? Any intuition?

In R

    n <- 20
    out <- replicate(1e5, {
      1-any(sample(n)==sample(n))
    })
    mean(out)
    > 0.3703

EDIT

Basen on the answers and comments, I found that I reinvented the wheel (although good exercise for me).
\begin{equation}
1-\sum_{i=1}^{n} \frac{(-1)^{k+1}}{k!} = 1+\sum_{i=1}^{n} \frac{(-1)^{k}}{k!} = \frac{(-1)^0}{0!} + \sum_{i=1}^{n} \frac{(-1)^{k}}{k!} = \sum_{i=0}^{n} \frac{(-1)^{k}}{k!} = \frac{!n}{n!}
\end{equation}

Thus, the simple answer is the number of derangements (subfactorial factor) over the number of combinations.

Best Answer

This is basically finding the number of derangements of $20$ elements over the number of possible arrangements $20!$. (Yes, this indeed is. We "set" the Monday arrangement. Then the Wednesday arrangement should have no similar seat for a person).

Then just search online regarding the number of derangement's closed form.

Related Question