Counting lattice paths by Narayana polynomials

Robert A. Sulanke

The electronic journal of combinatorics, Tome 7 (2000)

Résumé

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.

Détail

DOI : 10.37236/1518

Classification : 05A15
Mots-clés : Delannoy numbers, Narayana numbers, lattice paths