A Combinatorial Model for Lane Merging
Viktoriya Bardenova, Erik Insko, Katie Johnson, and
Shaun Sullivan
Department of Mathematics
Florida Gulf Coast University
Fort Myers, FL 33901
USA
Abstract:
A two-lane road approaches a stoplight. The left lane merges into the
right just past the intersection. Vehicles approach the intersection
one at a time, with some drivers always choosing the right lane, while
others always choose the shorter lane, giving preference to the right
lane to break ties. An arrival sequence of vehicles can be represented
as a binary string, where the zeros represent drivers always choosing
the right lane, and the ones represent drivers choosing the shorter
lane. From each arrival sequence we construct a merging path, which is a
lattice path determined by the lane chosen by each car. We give closed
formulas for the number of merging paths reaching the point (n, m) with
exactly k zeros in the arrival sequence, and the expected length of the
right lane for all arrival sequences with exactly k zeros. Proofs involve
an adaptation of André's reflection principle. Other interesting
connections also emerge, including to: ballot numbers, the expected
maximum number of heads or tails appearing in a sequence of n coin flips,
the largest domino snake that can be made using pieces up to [n : n],
and the longest trail on the complete graph Kn
with loops.
Full version: pdf,
dvi,
ps,
latex
(Concerned with sequences
A031940
A230137.)
Received May 20 2022; revised version received April 28 2023; May 19 2023; May 31 2023.
Published in Journal of Integer Sequences,
May 31 2023.
Return to
Journal of Integer Sequences home page