A Combinatorial Problem in Cinema Seating
Abstract
We address a problem concerning cinema audiences: ``A cinema has n seats numbered from $1$ to n, and there are n people with tickets numbered from $1$ to n. People enter the cinema in order. If someone has the ticket number i, they can choose seats whose numbers are multiples of i. They should exit the cinema if the permitted seats are occupied by previous audience members. In how many ways can they be seated under these conditions?" We give an algorithm to create the list of situations that meet these conditions. We also focus on finding the number of situations in two special cases: when exactly one seat is unoccupied whose total number is denoted by ω(n), and when all audiences 1, …, n−1 are seated, whose total number is denoted by ψ(n). Giving the recursive formula ψ(n)=1+∑d|n, d≠ nψ(d) with the initial value ψ(1)=1, we provide an explicit formula for ψ(pαqβ), where p and q are distinct prime numbers. Furthermore, we show that ω(n)=−n+∑i=1nψ(i).
Related
- A Combinatorial Approach to the CUE Joint Moment Problem
- Combinatorial Algorithms for Partial Inverse Min-Max Spanning Tree Problem under the Weighted Sum Hamming Distance
- An Exact Combinatorial Branch-and-Bound Algorithm for the Job Sequencing and Tool Switching Problem
- Combinatorial Optimization Augmented Machine Learning for Dynamic Electric Autonomous Dial-a-Ride Problem
- Fractional combinatorial Calabi flows on surfaces
BibTeX
@misc{mirzavaziri2026combinatorial,
title = {{A Combinatorial Problem in Cinema Seating}},
author = {Madjid Mirzavaziri and Daniel Yaqubi},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.22657},
eprint = {2609.22657},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.22657},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A Combinatorial Problem in Cinema Seating
AU - Madjid Mirzavaziri
AU - Daniel Yaqubi
PY - 2026
DA - 2026/09/19
PB - arXiv
DO - 10.48550/arxiv.2609.22657
UR - https://arxiv.org/abs/2609.22657
AB - We address a problem concerning cinema audiences: ``A cinema has n seats numbered from $1$ to n, and there are n people with tickets numbered from $1$ to n. People enter the cinema in order. If someone has the ticket number i, they can choose seats whose numbers are multiples of i. They should exit the cinema if the permitted seats are occupied by previous audience members. In how many ways can they be seated under these conditions?" We give an algorithm to create the list of situations that meet these conditions. We also focus on finding the number of situations in two special cases: when exactly one seat is unoccupied whose total number is denoted by ω(n), and when all audiences 1, …, n−1 are seated, whose total number is denoted by ψ(n). Giving the recursive formula ψ(n)=1+∑_d|n, d≠ nψ(d) with the initial value ψ(1)=1, we provide an explicit formula for ψ(p^αq^β), where p and q are distinct prime numbers. Furthermore, we show that ω(n)=−n+∑_i=1^nψ(i).
ER -