Generalizing Narayana and Schröder numbers to higher dimensions (Q1883671): Difference between revisions

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.