Counting lattice chains and Delannoy paths in higher dimensions

Lattice chains and Delannoy paths represent two different ways to progress through a lattice. We use elementary combinatorial arguments to derive new expressions for the number of chains and the number of Delannoy paths in a lattice of arbitrary finite dimension. Specifically, fix nonnegative integers n(1), ... , n(d), and let L denote the lattice of points (a(1), ... , a(d)) is an element of Z(d) that satisfy 0 <= a, <= n(i) for 1 <= i <= d. We prove that the number of chains in L is given by 2(nd+1) Sigma(k'max)(k=1)Sigma(k)(i=1)(-1)(i+k)((k - 1)(i - 1)) ((nd + k - 1)(nd)) Pi(d-1)(j=1) ((nj + i -1)(nj)). where k'(max) = n(1) + ... + n(d-1) + 1. We also show that the number of Delannoy paths in L equals Sigma(k'max)(k=1)Sigma(k)(i=1)(-1)(i+k)((k - 1)(i - 1)) ((nd + k - 1)(nd)) Pi(d-1)(j=1) ((nd + i -1)(nj)). Setting n(i) = n (for all i) in these expressions yields a new proof of a recent result of Duchi and Sulanke [9] relating the total number of chains to the central Delannoy numbers. We also give a novel derivation of the generating functions for these numbers in arbitrary dimension. (C) 2011 Elsevier B.V. All rights reserved.