The Diner Table Problem,
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 1/e-squared as n approaches infinity, 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. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 1980
- Accession Number
- ADA099175
Entities
People
- Bengt Aspvall
- Frank M. Liang
Organizations
- Stanford University