Counting Lattice Paths by Narayana Polynomials

Robert A. Sulanke

Abstract


Let $d(n)$ count the lattice paths from $(0,0)$ to $(n,n)$ using the steps (0,1), (1,0), and (1,1). Let $e(n)$ count the lattice paths from $(0,0)$ to $(n,n)$ with permitted steps from the step set ${\bf N} \times {\bf N} - \{(0,0)\}$, where ${\bf N}$ denotes the nonnegative integers. We give a bijective proof of the identity $e(n) = 2^{n-1} d(n)$ for $n \ge 1$. In giving perspective for our proof, we consider bijections between sets of lattice paths defined on various sets of permitted steps which yield path counts related to the Narayana polynomials.


Full Text: PDF