Catalan Traffic at the Beach

  • Heinrich Niederhausen

Abstract

We design a lattice path problem in ${\bf Z}^{2}$ (the Catalan traffic) with step set $\{\rightarrow,\uparrow\}$ strictly above the line $y=( x-1) /2$, and with step set $\{\downarrow,\searrow\}$ below that same line, except for the gates at $(2y,y)$ (with $\{\uparrow,\downarrow ,\searrow\}$-steps) and the closed intersections at $( 2y+1,y) $ (no traffic). The step sets prevent any traffic from going below the diagonal $y=-x$ (the beach). If we denote by $t(n,m)$ the number of paths from the origin to $(n,m)$, then the ubiquitous Catalan numbers $C_{n}={{2n}\choose {n}}/ ( n+1) $ occur as $t( n,-n) $ along the beach. We prove this with the help of hypergeometric identities, and also by solving an equivalent lattice path problem. On the way we pick up several identities and discuss other known sequences of numbers occurring in the Catalan traffic scheme, like the Motzkin numbers in row $m=-1$, and the "Tri-Catalan numbers" $1,1,3,12,55,\dots$ at the gates.

Published
2002-08-12
Article Number
R33