Séminaire Lotharingien de Combinatoire, B51c (2004), 16 pp.
Enrica Duchi and Robert A. Sulanke
The 2n-1 Factor for Multi-Dimensional Lattice
Paths with Diagonal Steps
Abstract.
In Zd,
let
D(n) denote the set of lattice paths from the origin to
(n,n,...,n) that use nonzero steps of the form
(x1,x2, ..., xd) where
xi is in { 0,1} for 1 <= i <= d.
Let S(n) denote the set of lattice paths from the origin to
(n,n,...,n) that use nonzero steps of the form
(x1,x2, ..., xd)
where xi >= 0 for 1 <= i <= d.
For d=3, we prove bijectively that the cardinalities
satisfy
|S(n)| = 2n-1 |D(n)|
for n= 1. One can extend our method to any dimension and obtain the same
identity. We find an explicit formula for |D(n)| when d=3.
Received: May 23, 2003.
Accepted: April 14, 2004.
Final Version: April 26, 2004.
The following versions are available: