Consider lattice paths in $d$ dimensions with the steps $X_1\mathrel{:=}(1,0,\dotsc,0)$, $X_2\mathrel{:=} (0,1,\dotsc,0)$,…, $X_d\mathrel{:=} (0,0,\dotsc,1)$. Let $\mathcal C(d, n)$ denote the set of lattice paths from $(0,0,\dotsc,0)$ to $(n,n,\dotsc,n)$ in the region $\{(x_1,x_2,\dotsc,x_d):0\le x_1\le x_2\le\dotsb\le x_d\}$. For any such lattice path $P:=p_1p_2\ldots p_{dn}$ with $dn$ steps, call $p_ip_{i+1}$ an ascent if $p_ip_{i+1}=X_jX_l$ for $j<l$.
Let $\operatorname{asc}(P)\mathrel{:=}\lvert\{i:\text{$p_ip_{i+1}$ is an ascent}\}\rvert$.
For $d\ge2$ and $0\le k\le(d−1)(n−1)$, let $N(d, n, k)\mathrel{:=}\lvert\{P\in\mathcal C(d, n):\operatorname{asc}(P)=k\}\rvert$.
Sulanke proved (Proposition 9 of Generalizing Narayana and Schröder numbers to higher dimensions, The Electronic Journal of Combinatorics 11 (2004), #R54):
$$\binom{n+d−1}{d}N(d, n, k)=\sum_{h=0}^d\binom{(d−1)(n−1)−k+h}{h}\binom{n+k+d−h−1}{d−h}N(d, n−1,k−h).$$
Can you provide a bijective proof of this, at least for $d=2$ or $d=3$?
$\begingroup$
$\endgroup$
Add a comment
|