کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4648650 | 1342422 | 2011 | 10 صفحه PDF | دانلود رایگان |
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 n1,…,ndn1,…,nd, and let LL denote the lattice of points (a1,…,ad)∈Zd(a1,…,ad)∈Zd that satisfy 0≤ai≤ni0≤ai≤ni for 1≤i≤d1≤i≤d. We prove that the number of chains in LL is given by 2nd+1∑k=1kmax′∑i=1k(−1)i+kk−1i−1nd+k−1nd∏j=1d−1nj+i−1nj, where kmax′=n1+⋯+nd−1+1. We also show that the number of Delannoy paths in LL equals ∑k=1kmax′∑i=1k(−1)i+k(k−1i−1)(nd+k−1nd)∏j=1d−1(nd+i−1nj). Setting ni=nni=n (for all ii) 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.
Journal: Discrete Mathematics - Volume 311, Issue 16, 28 August 2011, Pages 1803–1812