Number of monotone functions on a square grid

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.

• In the combinatorics literature, these sorts of maps are frequently studied as (reverse) plane partitions and (reverse) P-partitions. Mar 14, 2023 at 8:06
• In this case, a reverse plane partition with part size $\leq n$ is a map $\phi: [n]\times[n] \to [n]$ satisfying $\phi(a,b) \leq \phi(c,d)$ iff $a \leq c$ and $b \leq d$, so the number of such provides is the quantity you're looking for. MacMahon gave a product formula that counts them. Mar 14, 2023 at 8:16
• Thank you! Using the expression from mathworld.wolfram.com/PlanePartition.html, the answer is $2^{\Theta(n^2)}$. Mar 14, 2023 at 9:18
• Have the numbers been tabulated at oeis.org ? Mar 14, 2023 at 22:38
• @GerryMyerson: looks like they're sequence A008793 Mar 15, 2023 at 11:51

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)}$$.