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.

(reverse) plane partitionsand(reverse) P-partitions. $\endgroup$2more comments