Counting linearly ordered subsets of maximal length in partially ordered $d$-tuples of nonnegative integers

Question

Given $d\in \mathbb{N}$, let $X_d:= \{(\ell_1, \ldots , \ell_d): 0 \le \ell_1 \le \ldots \le \ell_d \le d\}\subset \mathbb{Z}^d$, and endow $X_d$ with the (usual) partial order, namely, $x\le y$ if and only if $x_j \le y_j$ for all $j=1,\ldots , d$. Note that if $Y\subset X_d$ is linearly ordered then $\# Y \le d^2 + 1$. Let $N_d$ be the number of linearly ordered subsets of $X_d$ of maximal length, that is, $N_d :=\# \{Y\subset X_d : Y \mbox{ linearly ordered, } \# Y = d^2 + 1\}$.

My question: Is there any neat expression available for $N_d$? If not, perhaps at least the asymptotics of $N_d$ as $d\to \infty$ can be worked out? Any answers or pertinent references will be much appreciated.

Answer 1

Denote $x!!=1!2!\cdots x!$. The number is $$N_d=\frac{(d-1)!!(d^2)!}{(2d-1)!!}\prod_{1\leqslant i<j\leqslant n}(j-i).$$ It can be interpreted as the number of lattice paths from $(0,\ldots,0)$ to $(d,\ldots,d)$ in $\mathbb{Z}^d$ such that all points on the path satisfy $x_1\leqslant x_2\leqslant\cdots\leqslant x_d$. More generally we might ask for the number of lattice paths from $(0,0,\ldots,0)$ to $(m_1,\ldots,m_d)\in\mathbb{Z}$ with $m_1\leqslant m_2\leqslant\cdots\leqslant m_d$ such that in every step $x_1\leqslant\cdots\leqslant x_d$. Using generating functions, these so-called lattice permutations are counted by Percy MacMahon in Combinatory Analysis, 1915-1916, chapter 5.

An alternative proof is by Doron Zeilberger: Andre's reflection proof generalized to the many-candidate ballot problem, Discrete Mathematics 44(3), 1983, 325-326.