On Packed Passenger Permutations
Abstract
An occupied seat in a binary row is called packed if both of its immediate neighbors are occupied. We give a self-contained combinatorial account of this statistic, equivalently the number of overlapping occurrences of 111. An occupied-block decomposition yields a coefficient formula at fixed occupancy and a direct proof of the sharp minimum max{0,3m-2n-2} for m passengers in n seats, including arrangements attaining the bound. The same decomposition gives a rational generating function, recurrences, expectations, and avoidance asymptotics. Full rows, in which every empty seat would become packed upon being filled, are related to independent sets of a path. A neighborhood-union expansion also gives exact counts on rectangular grids. The emphasis is a unified elementary presentation and explicit extremal constructions, rather than a new general enumeration method.
Related
- Distance-dependent patterns of intercity passenger mode share: A multiscale analysis of socioeconomic and spatiotemporal heterogeneity
- Short-term metro passenger flow forecasting via decoupled spatio-temporal modeling with a diffusion-convergence graph and Swin-Enhanced LSTM
- The Rule of Halves: the Holes of Every Close-Packed Stacking
- A Short Proof of Zhang's Conjecture on Stack-Sortable Permutations
- Recurrences for permutations with long increasing subsequences
BibTeX
@misc{dahlen2026packed,
title = {{On Packed Passenger Permutations}},
author = {Erik Dahlen},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.07204},
eprint = {2611.07204},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.07204},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - On Packed Passenger Permutations
AU - Erik Dahlen
PY - 2026
DA - 2026/11/04
PB - arXiv
DO - 10.48550/arxiv.2611.07204
UR - https://arxiv.org/abs/2611.07204
AB - An occupied seat in a binary row is called packed if both of its immediate neighbors are occupied. We give a self-contained combinatorial account of this statistic, equivalently the number of overlapping occurrences of 111. An occupied-block decomposition yields a coefficient formula at fixed occupancy and a direct proof of the sharp minimum max{0,3m-2n-2} for m passengers in n seats, including arrangements attaining the bound. The same decomposition gives a rational generating function, recurrences, expectations, and avoidance asymptotics. Full rows, in which every empty seat would become packed upon being filled, are related to independent sets of a path. A neighborhood-union expansion also gives exact counts on rectangular grids. The emphasis is a unified elementary presentation and explicit extremal constructions, rather than a new general enumeration method.
ER -