Suppose $X$ and $Y$ are two totally ordered sets with $|X| = n_X$ and $|Y|=n_Y$. We'll say an ordering ($\preceq$) of $X \times Y$ preserves the orderings of $X$ and $Y$ if for any elements $x_1,\,x_2 \in X$ and $y_1,\,y_2 \in Y$, we have $$x_1 \leq x_2 \implies (x_1, y_1) \preceq (x_2, y_1)$$ and similarly $$y_1 \leq y_2 \implies (x_1, y_1) \preceq (x_1, y_2)$$
How many orderings existing with this property?
This order preservation property naturally induces a partial ordering on $X \times Y$ and the number of linear extensions of a poset is a $\sharp P$-complete problem but given the natural structure of this order preservation, I'm hoping there may be a close-form solution or a polynomial-time algorithm that answers the question.
Best Answer
I will use $a$ and $b$ in place of $n_X$ and $n_Y$.
Linear extensions of the poset $X\times Y$ are in bijection with standard young tableaux whose underlying Ferrer's diagram is a an $a \times b$ rectangle. The number of standard young tableaux is enumerated by the hook length formula, which for a rectangle simplifies, assuming $a<b$, to $$ \frac{(ab)!}{1^1\cdot 2^2\cdots a^a\cdot (a+1)^a(a+2)^a\cdots b^a(b+1)^{a-1}(b+2)^{a-2}\cdots(a+b-1)^{1} } $$ This can be written more simply and symmetrically as $$ (ab)!\cdot \frac{(\prod_{k=1}^{a-1}k!)(\prod_{k=1}^{b-1}k!)}{(\prod_{k=1}^{a+b-1}k!)} $$ For example, when $a=b=3$, the number of posets would be $$9!\cdot \frac{1!\cdot 2!\cdot 1!\cdot 2!}{1!\cdot 2!\cdot 3!\cdot 4!\cdot 5!}=42.$$
For more information, see https://oeis.org/A060854, which references your problem directly.