Journal of Integer Sequences, Vol. 26 (2023), Article 23.5.3

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


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