Article ID Journal Published Year Pages File Type
9657738 Theoretical Computer Science 2005 14 Pages PDF
Abstract
Consider the 3-dimensional lattice paths running from (0,0,0) to (n,n,n), constrained to the region {(x,y,z):0⩽x⩽y⩽z}, and using various step sets. With C(3,n) denoting the set of constrained paths using the steps X≔(1,0,0), Y≔(0,1,0), and Z≔(0,0,1), we consider the statistic counting descents on a path P=p1p2…p3n∈C(3,n), i.e., des(P)≔|{i:pipi+1∈{YX,ZX,ZY},1⩽i⩽3n-1}|. A combinatorial cancellation argument and a result of MacMahon yield a formula for the 3-Narayana number, N(3,n,k)≔|{P∈C(3,n):des(P)=k+2}|. We define other statistics distributed by the 3-Narayana number and show that 4∑k2kN(3,n,k) yields the nth large 3-Schröder number which counts the constrained paths using the seven positive steps of the form (ξ1,ξ2,ξ3), ξi∈{0,1}.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
,