The 2n-1 Factor for Multi-Dimensional Lattice Paths with Diagonal Steps

Enrica Duchi ; Robert A. Sulanke

Séminaire lotharingien de combinatoire, Tome 51 (2004-2005)

Résumé

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₁,x₂, ..., 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₁,x₂, ..., 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.