15
$\begingroup$

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

$\endgroup$
16
  • $\begingroup$ $S_n$ does not have $n^2$ elements. $\endgroup$ Aug 17 '15 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 '15 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 '15 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 '15 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 '15 at 8:44
9
+25
$\begingroup$

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

UPDATE: I've added my counts to the OEIS as http://oeis.org/A261602 and http://oeis.org/A261603

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

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.

$\endgroup$
3
  • $\begingroup$ Gjergji Zaimi:Your answer is very useful!Thank you very much! $\endgroup$
    – user173856
    Sep 9 '15 at 2:02
  • $\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 '15 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 '15 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.