If $X$ and $Y$ are two ordered sets, how many orderings of $X \times Y$ exist that preserve the orderings of $X$ and $Y$?

Solution 1:

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.