Report Number: CS-TR-80-829
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