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).

  • $\begingroup$ How do you came up with this question? It seems there should be an interesting context in which this task arises. $\endgroup$ Sep 7 '17 at 16:04
  • $\begingroup$ 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. $\endgroup$
    – Skrodde
    Sep 8 '17 at 15:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.