Number of monotone functions on a square grid

Question

How many monotone mappings $[n] \times [n] \to [n]$ exist? Here:

• $[n]$ denotes $\{1, 2, \ldots, n\}$,
• Monotone means that if $x_1 \le x_2$ and $y_1 \le y_2$, then $f(x_1, y_1) \le f(x_2, y_2)$.

I'm interested in the answer up to $2^{\Theta(\cdot)}$-notation. To give an example, I would be absolutely happy if the answer is $2^{\Theta(n \log n)}$, while $2^{\Theta(n^2)}$ would kill my idea. Anything strictly less than $2^{\Theta(n^2)}$ would be an improvement for me, but I would like an upper bound with a quasi-linear exponent (if it exists, of course).

If we instead consider monotone $[n] \to [n]$, then the number of mappings is around $\binom{2n-1}{n}$ (we can think of it as $2n - 1$ balls, where $n$ balls represent the numbers $1, \ldots, n$, and remaining $n-1$ balls represent positions where the function value increases by $1$). I've tried to apply this idea to the $[n]^2 \to n$, but I failed to utilize monotonicity on both arguments, and could only get $n^{O(n^2)}$.

The answer for $[n]^2 \to [n]$ is clearly between $n^{\Theta(n)}$ (we get this much even for $[n] \to [n]$) and $n^{n^2}$ (it's the number of all possible functions $[n]^2 \to [n]$).

I'm also interested in the same question for mapping $[n]^d \to [n]$, where $d \in \mathbb N$ (and, in computer science terms, $d$ is not a fixed parameter).

Dedekind numbers answer the question for monotone boolean functions, which can be thought of as $[2]^d \to [2]$.

P.S.: No idea which tags to use.

Answer 1

Thanks to Alex Lazar for referring me to the right keywords.

This is called something like "the number of plane partitions that fit inside the $n \times n \times n$ box", and can be computed as : $$ PL(n,n,n)=\frac{G^3(n+1) \cdot G(3n+1)}{G^3(2n+1)}, $$ where $G$ is the Barnes G-function. Mathematica tells me that the highest-order term in the Taylor expansion of its natural logarithm is $$\frac 32 (3 \ln 3 - 4 \ln 2) n^2 \approx 0.785 n^2.$$ So the answer to my question is $2^{\Theta(n^2)}$.