Let $n>1$ be a given positive integer. For any $0\leq k\leq n^2$, let $A_k$ be the set of permutations $((i_1,j_1),(i_2,j_2),\cdots,(i_{n^2},j_{n^2}))$ of the ordered pairs $(1,1),(1,2),\cdots,(1,n),\cdots,(n,1),(n,2),\cdots,(n,n)$ satisfying $i_1\leq i_2\leq \cdots\leq i_k$ and $j_{k+1}\leq j_{k+2}\leq \cdots\leq j_{n^2}$.
For any $$((i_1,j_1),(i_2,j_2),\cdots,(i_k,j_k),(i_{k+1},j_{k+1}),\cdots,(i_{n^2},j_{n^2}))\in A_k,$$ we have $$((j_{k+1},i_{k+1}),(j_{k+2},i_{k+2}),\cdots,(j_{n^2},i_{n^2}),(j_1,i_1),(j_2,i_2),\cdots,(j_k,i_k))\in A_{n^2-k}.$$
So it is easy to see that $\vert A_k\vert=\vert A_{n^2-k}\vert$ for any $0\leq k\leq [n^2/2]$.
Question: Do we have that $\vert A_0\vert<\vert A_1\vert<\cdots<\vert A_{[n^2/2]}\vert$?
Best Answer
UPDATE (2022-07-13). The generating function for $A_k$ can be expressed as $$\sum_{k\geq0} A_k t^k = {\cal L}_{x_1,\dots,x_n,y_1,\dots,y_n} \sum_{\lambda} e_{\lambda}(x_1,\dots,x_n)\cdot m_{\bar\lambda}(y_1,\dots,y_n)\cdot t^{\mathrm{sum}(\lambda)},$$ where summation is done over all partitions $\lambda$ whose Young tableau fits the $n\times n$ square; $\bar\lambda$ is the partition whose Young tableau complements that of $\lambda$ in the $n\times n$ square; $e$ and $m$ are elementary and monomial symmetric polynomials respectively; and $\cal L$ is the Laplace transform evaluated at $1$, which replaces each $x_i^d$ or $y_j^d$ with $d!$.
With this formula I was able to extend computations and confirm the conjecture for $n\leq 10$. The data is uploaded to OEIS A261602 and OEIS A261603.
Below is my original answer presenting data for $n\leq 6$.
I've computed values of $|A_k|$ for $0\leq k\leq \lfloor n^2/2\rfloor$ and $n\leq 6$:
$n=1:$ 1
$n=2:$ 4, 8, 10
$n=3:$ 216, 648, 1188, 1668, 1944
$n=4:$ 331776, 1327104, 3151872, 5695488, 8608896, 11446272, 13791744, 15326208, 15858432
$n=5:$ 24883200000, 124416000000, 360806400000, 787138560000, 1426595328000, 2262299258880, 3240594432000, 4283587584000, 5304730521600, 6222411878400, 6968709089280, 7493189990400, 7763310604800
$n=6:$ 139314069504000000, 835884417024000000, 2855938424832000000, 7259810955264000000, 15220062093312000000, 27765294052147200000, 45532546213478400000, 68600569724928000000, 96440964380098560000, 127985462154362880000, 161777817980986982400, 196164002436769382400, 229476155622594969600, 260178812386069708800, 286962944406552576000, 308788668410898677760, 324887962565624463360, 334743605500457779200, 338060641751949312000
So the conjecture is confirmed numerically for $n\leq 6$.