# Bound on number of nxn grids with lexicographical ordering / poset structure

Given $n\in\mathbb{N}$, consider the numbers $\{1,\ldots,n^2\}$ and a permutation $\pi\in S_{n^2}$. It induces pairs $(1,\pi(1))$, $\ldots$, $(n^2,\pi(n^2))$.

Consider an $n\times n$ grid. How many possibilities are there to place the pairs in the grid such that each row grows from left to right in the first value of the pair, while each column grows from top to bottom in the second value?

e.g. $n=3$, some $\pi\in S_9$, a valid placement would be:

\begin{align*} (1,2) && (2,1) && (3,3)\\ (4,4) && (5,5) && (9,6)\\ (6,7) && (7,8) && (8,9) \end{align*}

For the the $\pi$, the following placement is not valid as the lower left $(8,9)$ has a larger first-coordinate (8) than the lower middle $(6,7)$ has (6).

\begin{align*} (1,2) && (2,1) && (3,3)\\ (4,4) && (5,5) && (9,6)\\ (8,9) && (6,7) && (7,8) \end{align*}

It seeems to me that it is somewhat hard to find an exact value for the number of valid placements for a given permutation $\pi$. Therefore, a hopefully easier, less accurate question: Is the above number always smaller or equal than the number for the specific permutation $\pi=id$?

In case of $\pi=id$, the number of valid placements is given by this sequence, which denotes the number of Young Tableaus of shape $(n,\ldots,n)$ or the number of linear extensions of the $n\times n$ lattice (see this question).

• How do you came up with this question? It seems there should be an interesting context in which this task arises. Sep 7, 2017 at 16:04
• Artsem, the question arose in the context of orderings of geometrical points in two-dimensional euclidean space. We would like to order $n^2$ points lexicographically in an $n\times n$ grid. To do this, we devised an algorithm. But the optimality of the algorithm depends on the number of possible outcomes, which is exactly the above question. Sep 8, 2017 at 15:36
• One can ask the same for a general shape $\lambda \vdash n$, and pairs $(1,\sigma_1),\dotsc, (n,\sigma_n)$, where one instead count 'standard' Young tableaux compatible with $\sigma$. I wonder if there is some nice counting-formula here, if the permutation or the shape is chosen in nice ways. Aug 2, 2022 at 9:01

Let $$(P,\le_P)$$ and $$(Q,\le_Q)$$ be posets, although usually we will just refer to "$$P$$" and "$$Q$$". One can define a partial ordering $$\le$$ on the direct product $$P\times Q$$ as follows: $$(p,q)\le(p',q')$$ if $$p\le_P p'$$ and $$q\le_Q q'$$.

A function $$f$$ from $$P$$ to $$Q$$ is order-preserving if for all $$p,p'\in P$$, $$p\le_P p'$$ implies $$f(p)\le_Q f(p')$$.

You are considering certain subsets of $$n^2$$ points in $$\mathbb N\times\mathbb N$$ and regarding them as subposets.

If $$\bf n$$ is the $$n$$-element totally ordered set, you are interested in counting the number of bijective order-preserving maps from $$\bf n\times\bf n$$ onto one of the aforementioned subposets of $$\mathbb N\times\mathbb N$$.

The subset obtained from $$\pi=id$$ is a totally ordered set order-isomorphic to $$\bf{n^2}$$.

For any other $$\pi$$, this poset $$Q_\pi$$ will not be a totally ordered set, since there will be $$a,b,c,d\in\mathbb N$$ such that $$1\le a and $$1\le d < c\le n^2$$ but your poset has the pairs $$(a,c)$$ and $$(b,d)$$ and $$(a,c)\nleq(b,d)$$ and $$(b,d)\nleq (a,c)$$.

Any poset $$(P,\le_P)$$ has a linear extension (Szilprajn's Theorem): there is a totally ordered set $$(L,\le_L)$$ and an order-preserving bijection from $$P$$ onto $$L$$.

Fix such a map $$\lambda$$ from $$Q_\pi$$ onto such an $$L$$, which is order-isomorphic to $${\bf n^2}$$, or $$Q_{id}$$.

Now any order-preserving bijection $$b$$ from $$\bf n\times\bf n$$ onto $$Q_\pi$$ can be composed with $$\lambda$$ and we still get an order-preserving bijection onto $$Q_{id}$$. This map $$b\mapsto \lambda\circ b$$ is one-to-one since $$\lambda$$ has an inverse (as a map of sets).

It's 6:32 a.m., but this looks right. Is it?

We have indeed found a proof based on an injection of the set of valid placements into the set of valid placements of the identity permutation. Find details in Theorem 9 of Version 4 of this ArXiv paper: https://arxiv.org/pdf/1710.03435.pdf.