Paper detail

Bijections for pairs of non-crossing lattice paths and walks in the plane

It is a classical result in combinatorics that among lattice paths with 2m steps U=(1,1) and D=(1,-1) starting at the origin, the number of those that do not go below the x-axis equals the number of those that end on the x-axis. A much more unfamiliar fact is that the analogous equality obtained by replacing single paths with k-tuples of non-crossing paths holds for every k. This result has appeared in the literature in different contexts involving plane partitions (where it was proved by Proctor), partially ordered sets, Young tableaux, and lattice walks, but no bijective proof for k>1 seems to be known. In this paper we give a bijective proof of the equality for k=2, showing that for pairs of non-crossing lattice paths with 2m steps U and D, the number of those that do not go below the x-axis equals the number of those that end on the x-axis. Translated in terms of walks in the plane starting at the origin with 2m unit steps in the four coordinate directions, our work provides correspondences among those constrained to the first octant, those constrained to the first quadrant that end on the x-axis, and those in the upper half-plane that end at the origin. Our bijections, which are defined in more generality, also prove new results where different endpoints are allowed, and they give a bijective proof of the formula for the number of walks in the first octant that end on the diagonal, partially answering a question of Bousquet-Mélou and Mishna.