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

  • $\begingroup$ $S_n$ does not have $n^2$ elements. $\endgroup$ Aug 17, 2015 at 12:03
  • $\begingroup$ 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. $\endgroup$
    – Boris Bukh
    Aug 17, 2015 at 13:23
  • 2
    $\begingroup$ 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. $\endgroup$ Aug 22, 2015 at 8:51
  • 2
    $\begingroup$ Better to call it a linear order of the $n^2$ pairs than a permutation. $(abcd)$ and (cdab)$ are equal as permutations. $\endgroup$ Aug 28, 2015 at 6:19
  • 2
    $\begingroup$ $A_{0} = (n!)^n$ (trivial), $A_{1} = n(n!)^n$ (provable), $A_{2} = (n!)^n (n^2+n-1)/2$ (conjecture; must be provable too). It gets very messy with $k\ge 3$. $\endgroup$
    – zhoraster
    Aug 28, 2015 at 8:44

2 Answers 2


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

  • $\begingroup$ Thank you! Is it possible to compute the values of $\vert A_k\vert$ for $n=6$? $\endgroup$
    – user173856
    Aug 24, 2015 at 3:38
  • $\begingroup$ @user173856: I've just extended my computation to $n=6$. $\endgroup$ Aug 25, 2015 at 3:18

This is not an answer, but perhaps a relevant thought. The combinatorial description of $A_k$, for $0\le k\le n^2$, together with the Gamma integral $\Gamma(n+1)=\int_0^{\infty}x^ne^{-x}dx$ leads to the generating function $$\sum_{k=0}^{n^2} A_kt^k=\int_0^\infty\cdots \int_0^{\infty}e^{-\sum_{i=1}^n(x_i+y_i)}\prod_{i,j=1}^n(x_i+ty_j)dx_1dy_1\cdots dx_ndy_n.$$ A polynomial whose coefficients form a unimodal (resp. log-concave) sequence is called a unimodal (resp. log-concave) polynomial. It is known that a polynomial with real roots is log-concave and thus unimodal. So unimodality holds for the polynomial being integrated above. Unfortunately log-concavity or unimodality are not preserved under linear combinations so one can't conclude the desired property just from the integral representation above. Maybe someone with knowledge in analysis will find this wording more useful.

  • $\begingroup$ Gjergji Zaimi:Your answer is very useful!Thank you very much! $\endgroup$
    – user173856
    Sep 9, 2015 at 2:02
  • 1
    $\begingroup$ Possible bad news for this strategy: $\sum A_k t^k$ does not have real roots. Using Max Alekseyev's numbers, all the roots of $4 x^4 + 8 x^3 + 10 x^2 + 8 x + 4$ are complex. On the other hand, his data is consistent so far with the coefficients being log concave. $\endgroup$ Sep 24, 2015 at 19:05
  • 1
    $\begingroup$ @DavidSpeyer But all the roots have $\Re(z) < 0$, so it is real-stable, which means there might be more to this strategy? $\endgroup$
    – Suvrit
    Sep 24, 2015 at 19:38

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.