# A question about certain sets of permutations of the ordered pairs $(1,1),(1,2),\cdots,(1,n),\cdots,(n,1),(n,2),\cdots,(n,n)$

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$?

• $S_n$ does not have $n^2$ elements. Aug 17, 2015 at 12:03
• I do not understand the definition of $A_k$. As written, $A_k$ consists of $n^2$-tuples of certain kind of pairs, not of permutations. Aug 17, 2015 at 13:23
• Another way to define it: $|A_k|$ is the number of $n\times n$ matrices with entries $1,\ldots,n^2$ (once each), such that $1,\ldots,k$ are in row order and $k+1,\ldots,n^2$ are in column order. Aug 22, 2015 at 8:51