Institution: Stanford University, Department of Computer Science

Title: The dinner table problem

Author: Aspvall, Bengt

Author: Liang, Frank M.

Date: December 1980

Abstract: This report contains two papers inspired by the "dinner table problem": If n people are seated randomly around a circular table for two meals, what is the probability that no two people sit together at both meals? We show that this probability approaches $e^{-2}$ as $n \rightarrow \infty$, and also give a closed form. We then observe that in many similar problems on permutations with restricted position, the number of permutations satisfying a given number of properties is approximately Poisson distributed. We generalize our asymptotic argument to prove such a limit theorem, and mention applications to the problems of derangements, menages, and the asymptotic number of Latin rectangles.

http://i.stanford.edu/pub/cstr/reports/cs/tr/80/829/CS-TR-80-829.pdf