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](https://oeis.org/A039622), 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](https://mathoverflow.net/questions/280316/linear-extension-of-the-n-times-n-lattice)). 



Bound on number of nxn grids with lexicographical ordering / poset structure
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>.


