Generalizing Narayana and Schröder numbers to higher dimensions. (English) Zbl 1057.05006
Summary: Let \({\mathcal C}(d,n)\) denote the set of \(d\)-dimensional lattice paths using the steps \(X_1:=(1,0,\dots,0)\), \(X_2:=(0,1,\dots, 0),\dots,X_d:=(0,0,\dots,1)\), running from \((0,0,\dots,0)\) to \((n,n,\dots,n)\), and lying in \(\{(x_1,x_2,\dots, x_d):0\leq x_1\leq x_2\leq\cdots\leq x_d\}\). On any path \(P:=p_1p_2\dots p_{dn}\in{\mathcal C}(d,n)\), define the statistics \(\text{asc}(P):=|\{i:p_ip_{i+1}=X_jX_\ell\), \(j<\ell\}|\) and \(\text{des}(P):=|\{i:p_ip_{i+1}=X_jX_\ell,j>\ell\}|\). Define the generalized Narayana number \(N(d,n,k)\) to count the paths in \({\mathcal C} (d,n)\) with \(\text{asc}(P)=k\). We consider the derivation of a formula for \(N(d,n,k)\), implicit in MacMahon’s work. We examine other statistics for \(N(d,n,k)\) and show that the statistics asc and des\(-d+1\) are equidistributed. We use Wegschaider’s algorithm, extending Sister Celine’s (Wilf-Zeilberger) method to multiple summation, to obtain recurrences for \(N(3,n,k)\). We introduce the generalized large Schröder numbers \((2^{d-1}\sum_k N(d,n,k) 2^k)_{n\geq 1}\) to count constrained paths using step sets which include diagonal steps.
MSC:
05A15 | Exact enumeration problems, generating functions |
Software:
OEISOnline Encyclopedia of Integer Sequences:
3-dimensional Catalan numbers.Triangle of 3-Narayana numbers, N(n,k), for n >= 1, 0 <= k <= 2n-2.
Number of 3-dimensional lattice paths running from (0,0,0) to (n,n,n), lying in {(x,y,z) : 0<=x<=y<=z} and using the steps (1,0,0), (0,1,0), (0,0,1), (1,1,0), (1,0,1), (0,1,1), (1,1,1).
Three-dimensional small Schroeder numbers.