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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .