Random unfriendly seating arrangement in a dining table

DOI10.1016/J.AAM.2015.01.002MaRDI QIDQ2343189zbMATH OpenOpenAlexFDO

Authors Hua-Huai Chern, Hsien-Kuei Hwang, Tsung-Hsi Tsai

Publication date 4 May 2015

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1406.0614

zbMATH Keywords

generating functionsreccurence relationssurprising counter examples

Mathematics Subject Classification ID

Combinatorial probability (60C05) Geometric probability and stochastic geometry (60D05) Inequalities; stochastic orderings (60E15) Central limit and other weak theorems (60F05)

Abstract: A detailed study is made of the number of occupied seats in an unfriendly seating scheme with two rows of seats. An unusual identity is derived for the probability generating function, which is itself an asymptotic expansion. The identity implies particularly a local limit theorem with optimal convergence rate. Our approach relies on the resolution of Riccati equations.

Review text

In this article, the so called ``unfriendly seating problem is analysed for \(2\times n\) dimensions. The general problem \((m\times n)\) has been stated in the sixties and solved for \(1\times n\) (expected number of occupied seats, error relation). Here, it is shown that the \(2\times n\) problem has some surprising properties compared with the \(1\times n\) problem:{\parindent=0.7cm\begin{itemize}\item[--] There exists a configuration with more empty seats available and the expected value of occupied seats is lower than the configuration with less seats.\item[--] Also a configuration is shown with more empty seats available and the probability of having more people seated is lower than the probability for a configuration with less seats. \end{itemize}} For the \(2\times n\) problem, a recurrence relation is developed and, using this recurrence, a differential equation (of Riccati type) for the corresponding generating functions is stated and solved. The main result is an expected value (of occupied seats) and an error bound for all \(n\). For large \(n\) (the limit of \(n\) going to infinity, respectively) the distribution is shown to be asymptotically normal. At the end, the dynamic approach of seating people is compared with the combinatorial approach (counting all possible seatings) and the main result is that the ``space utilization is better in the sequential model than in the combinatorial model.

Recommendations

• Random maximal independent sets and the unfriendly theater seating arrangement problem
• The dinner table problem: the rectangular case
• Seating rearrangements on arbitrary graphs
• The Freshman's Approach to Conway's Napkin Problem
• On the `problème des ménages' from a probabilistic viewpoint

Cites work

• A generating functions approach for the analysis of grand averages for multiple QUICKSELECT
• AN EXAMPLE IN THE THEORY OF THE SPECTRUM OF A FUNCTION
• Analytic combinatorics
• Asymptotic normality in vacancies on a line
• Discrete Spacings
• Exact and approximate results for deposition and annihilation processes on graphs
• Existence and spatial limit theorems for lattice and continuum particle systems
• scientific article; zbMATH DE number 3151126 (Why is no real title available?)
• scientific article; zbMATH DE number 3164960 (Why is no real title available?)
• scientific article; zbMATH DE number 1080355 (Why is no real title available?)
• scientific article; zbMATH DE number 2018401 (Why is no real title available?)
• scientific article; zbMATH DE number 3396865 (Why is no real title available?)
• Limit theorems for monotonic particle systems and sequential deposition.
• Mellin transforms and asymptotics: Finite differences and Rice's integrals
• On convergence rates in the central limit theorems for combinatorial structures
• On the Lambert \(w\) function
• Random maximal independent sets and the unfriendly theater seating arrangement problem
• Random sequential adsorption on a ladder
• Random sequential packing of cubes

Cited in

(12)

• A combinatorial approach for discrete car parking on random labelled trees
• Seating rearrangements on arbitrary graphs
• Sitting down for dinner at a twin convention
• Finding your seat versus tossing a coin
• Per-site occupancy in the discrete parking problem
• On avoiding a clash of arms at a round table
• The Freshman's Approach to Conway's Napkin Problem
• The 2 n seating derangements
• The dinner table problem: the rectangular case
• Complexity function of jammed configurations of Rydberg atoms
• A model of random sequential adsorption on a ladder graph
• Parking triangles on a continuous ladder

This page was built for publication: Random unfriendly seating arrangement in a dining table

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2343189)