Journal of Integer Sequences, Vol. 24 (2021), Article 21.2.8

Between Broadway and the Hudson: A Bijection of Corridor Paths

Nachum Dershowitz
School of Computer Science
Tel Aviv University
Ramat Aviv


We present a substantial generalization of the equinumeracy of Grand Dyck paths and Dyck-path prefixes, constrained within a band. The number of constrained paths starting at level i and ending in a window of size 2j + 2 is equal to the number starting at level j and ending in a window of size 2i + 2 centered around the same point. A new encoding of lattice paths provides a bijective proof.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A000007 A000012 A000045 A000244 A001519 A003462 A005021 A007051 A011782 A016116 A024175 A025192 A028495 A030436 A033191 A038754 A052975 A060557 A061551 A080936 A080937 A080938 A087944 A087946 A094789 A094790 A124302 A178381 A211216 A336675 A336678.)

Received January 13 2021; revised versions received January 14 2021; January 27 2021; January 30 2021. Published in Journal of Integer Sequences, January 30 2021.

Return to Journal of Integer Sequences home page