Catalan traffic at the beach

Heinrich Niederhausen

The electronic journal of combinatorics, Tome 9 (2002)

Résumé

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.

Détail

DOI : 10.37236/1649

Classification : 05A15, 05A19
Mots-clés : Catalan numbers, hypergeometric identities, lattice path, Motzkin numbers