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.