5
$\begingroup$

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.

$\endgroup$
7
  • 1
    $\begingroup$ In the combinatorics literature, these sorts of maps are frequently studied as (reverse) plane partitions and (reverse) P-partitions. $\endgroup$
    – Alex Lazar
    Commented Mar 14, 2023 at 8:06
  • 1
    $\begingroup$ 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. $\endgroup$
    – Alex Lazar
    Commented Mar 14, 2023 at 8:16
  • $\begingroup$ Thank you! Using the expression from mathworld.wolfram.com/PlanePartition.html, the answer is $2^{\Theta(n^2)}$. $\endgroup$
    – Dmitry
    Commented Mar 14, 2023 at 9:18
  • $\begingroup$ Have the numbers been tabulated at oeis.org ? $\endgroup$ Commented Mar 14, 2023 at 22:38
  • $\begingroup$ @GerryMyerson: looks like they're sequence A008793 $\endgroup$
    – Alex Lazar
    Commented Mar 15, 2023 at 11:51

1 Answer 1

3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Please accept your answer so the question gets listed as accepted. $\endgroup$
    – JoshuaZ
    Commented Mar 14, 2023 at 18:58
  • $\begingroup$ @JoshuaZ, it said that I can do this in 2 days. $\endgroup$
    – Dmitry
    Commented Mar 14, 2023 at 19:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.