Counting Lattice Paths by Narayana Polynomials

  • Robert A. Sulanke


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.

Article Number