#####
Séminaire Lotharingien de Combinatoire, B51c (2004), 16 pp.

# Enrica Duchi and Robert A. Sulanke

# The 2^{n-1} Factor for Multi-Dimensional Lattice
Paths with Diagonal Steps

**Abstract.**
In **Z**^{d},
let
**D**(*n*) denote the set of lattice paths from the origin to
(*n,n,...,n*) that use nonzero steps of the form
(*x*_{1},*x*_{2}, ..., *x*_{d}) where
*x*_{i} 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
(*x*_{1},*x*_{2}, ..., *x*_{d})
where *x*_{i} >= 0 for 1 <= *i* <= *d*.
For *d*=3, we prove bijectively that the cardinalities
satisfy
|**S**(*n*)| = 2^{n-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: