Об исследовании числа перестановок с заданными инверсиями.

[e7e5]

Последовательность описывается в OEIS
http://oeis.org/A000140

Изучается отношение
$M(n)/M(n-1)$, здесь $M(n)$ максимальный элемент в строке $n$

Утверждается, что $M(n)/M(n-1)=n+1/2$ при $n \to \infty$

Кто может доказать или опровергнуть это утверждение?

для $n$ от $0$ до $149$ имеем

1.00000000, 1.00000000, 2.00000000, 3.00000000, 3.66666667, 4.59090909, 5.67326733, 6.69458988, 7.61939520, 8.57906801, 9.60953383, 10.6235009, 11.5884536, 12.5657349, 13.5817521, 14.5907723, 15.5704306, 16.5558579, 17.5656455, 18.5718445, 19.5585507, 20.5484134, 21.5549876, 22.5594838, 23.5501133, 24.5426559, 25.5473665, 26.5507683, 27.5438066, 28.5380914, 29.5416285, 30.5442887, 31.5389122, 32.5343930, 33.5371446, 34.5392804, 35.5350028, 36.5313400, 37.5335406, 38.5352923, 39.5318079, 40.5287792, 41.5305788, 42.5320411, 43.5291478, 44.5266018, 45.5281005, 46.5293394, 47.5268986, 48.5247283, 49.5259956, 50.5270586, 51.5249718, 52.5230999, 53.5241854, 54.5251073, 55.5233026, 56.5216716, 57.5226117, 58.5234188, 59.5218427, 60.5204088, 61.5212309, 62.5219434, 63.5205550, 64.5192845, 65.5200094, 66.5206430, 67.5194106, 68.5182772, 69.5189212, 70.5194882, 71.5183871, 72.5173696, 73.5179455, 74.5184560, 75.5174660, 76.5165477, 77.5170657, 78.5175276, 79.5166329, 80.5157998, 81.5162682, 82.5166882, 83.5158756, 84.5151165, 85.5155421, 86.5159256, 87.5151843, 88.5144896, 89.5148781, 90.5152297, 91.5145507, 92.5139127, 93.5142686, 94.5145921, 95.5139679, 96.5133798, 97.5137071, 98.5140058, 99.5134299, 100.512886, 101.513188, 102.513465, 103.512932, 104.512428, 105.512707, 106.512964, 107.512470, 108.512001, 109.512260, 110.512499, 111.512039, 112.511602, 113.511843, 114.512067, 115.511637, 116.511229, 117.511454, 118.511663, 119.511261, 120.510879, 121.511090, 122.511285, 123.510909, 124.510550, 125.510748, 126.510932, 127.510578, 128.510241, 129.510426, 130.510599, 131.510267, 132.509949, 133.510123, 134.510286, 135.509973, 136.509673, 137.509838, 138.509992, 139.509696, 140.509412, 141.509568, 142.509713, 143.509434, 144.509165, 145.509312, 146.509450, 147.509185, 148.508930,

[Хорхе]

Мысли вслух.

Производящая функция двух переменных (где $z$ отмечает элементы перестановки, а $q$ инверсии), экспоненциальная по $z$ и простая по $q$, равна

$$ F(z,q) = \sum_{n\ge 0} \frac{z^n}{n!} \prod_{k=1}^n (1+q+\dots+q^{k-1}) = \sum_{n\ge 0} \frac{z^n}{(1-q)^n n!} \prod_{k=1}^n (1-q^k) = \sum_{n\ge 0} \frac{t^n (q;q)_n}{ n!}, $$

$t=z/(1-q)$. Пахнет какими-то $q$-рядами. Я тут абсолютный профан. Кто знает, что хорошего или плохого можно сказать об этом ряде? Вообще выглядит он как-то совсем классически.

-- Вс ноя 14, 2010 19:41:44 --

Можно, конечно, брать обычную производящую функцию по $z$. Тогда

$$ G(z,q) = \sum_{n\ge 0}(z/(1-q))^n (q;q)_n = \frac{1}{(t;q)_\infty} = \prod_{k\ge 0}\frac{1}{ 1-\frac{z q^n}{1-q}}. $$

Не самая лучшая формула, конечно, но хоть что-то.

Самое плохое в ней, конечно, то, что нельзя подставить $q=1$, хотя очень нужно.

[e7e5]

Хорхе в сообщении #375104 писал(а):

Мысли вслух.

$$ G(z,q) = \sum_{n\ge 0}(z/(1-q))^n (q)_n = \frac{1}{(t;q)_\infty} = \prod_{k\ge 0}\frac{1}{ 1-\frac{z q^n}{1-q}}. $$

Не самая лучшая формула, конечно, но хоть что-то.

Самое плохое в ней, конечно, то, что нельзя подставить $q=1$, хотя очень нужно.

И как же быть?

[Хорхе]

Вот почитываю на досуге, что с этими $q$-рядами люди делают. Сложно, но безумно интересно. Если чего пойму, напишу.

-- Вт ноя 16, 2010 17:27:38 --

Кстати, я только что заметил, что я неправильно последнюю формулу написал (было б хорошо, если бы она была верна). То, что я написал в правой части, это $\sum_{n\ge 0} \frac{t^n}{(q;q)_n}$.

[e7e5]

Хорхе в сообщении #375958 писал(а):

Вот почитываю на досуге, что с этими $q$-рядами люди делают. Сложно, но безумно интересно. Если чего пойму, напишу.

Вопрос сложный. С интересом будет узнать, чего узнаете, в том числе применительно к заданному вопросу-утверждению ( либо доказать, либо опровергуть).

[e7e5]

e7e5 в сообщении #374890 писал(а):

Последовательность описывается в OEIS
http://oeis.org/A000140
$M(n)$ максимальный элемент в строке $n$

Какая может быть методика оценки этого максимального элемента в строке?

[e7e5]

Для чисел Кендел-Мана

1, 1, 2, 6, 22, 101, 573, 3836, 29228, 250749, 2409581, 25598186, 296643390, 3727542188, 50626553988, 738680521142, 11501573822788, 190418421447330, 3344822488498265, 62119523114983224

http://oeis.org/A000140 есть гипотеза:
$M(n+1)/M(n) \to (n-0.5)$, $n \to \infty$, $M(n)$ - max элемент в строке $n$
$M(1)=1$, $M(2)/M(1)=1$, $2=M(3)/M(2)$,... $28.5380914=M(30)/M(29)$

1.00000000, 1.00000000, 2.00000000, 3.00000000, 3.66666667, 4.59090909, 5.67326733, 6.69458988, 7.61939520, 8.57906801, 9.60953383, 10.6235009, 11.5884536, 12.5657349, 13.5817521, 14.5907723, 15.5704306, 16.5558579, 17.5656455, 18.5718445, 19.5585507, 20.5484134, 21.5549876, 22.5594838, 23.5501133, 24.5426559, 25.5473665, 26.5507683, 27.5438066, 28.5380914,

В качестве подсказки предлагается такая идея:
Предположим, мы рассматриваем перестановки из $(n-1)$ элемента, лежащие в "максимальной группе" (то есть те перестановки, у которых число инверсий "критическое", то есть количество таких перестановок как раз $M(n-1))$. Затем рассмотрим перестановки из $n$ элементов, лежащие в "максимальной группе"(их количество равно $M(n))$. Есть ли простой способ доказать, что каждой перестановке в первой группе соответствует примерно $(n-2)$ перестановки во второй группе? А еще лучше, если примерно половине перестановок в первой группе соответствует $(n-2)$ перестановки во второй группе, а еще половине перестановок - (n-1) перестановка во второй группе(т.е. $M(n)/M(n-1)$ примерно равно $n-1.5$).

Другими словами, предлагается рассмотреть соответствующие множества перестановок и поискать какое-то соответствие между этими множествами перестановок, которе бы указывало на то, как растет число перестановок в n-ом множестве относительно $(n-1)$-ого множества , грубо говоря, с точки зрения комбинаторики. А потом, переформулируя это утверждение в виде формулы, получить искомый результат.

Нащупать комбинаторную связсь между множествами не получается. Пожалуйста помогите

[sup]

Я бы попробовал работать с интегральными представлениями, а не с комбинаторикой. Ваша гипотеза наводит на мысль, что здесь, похоже, "зарыта" Г-функция. Тогда уж лучше попробовать интегралы и асимптотические оценки.
Рассмотрим перестановки из $n$ элементов. Как уже отмечалось, прозводящая функция для числа перестановок с заданным количеством инверсий

$$F(q)=\frac{\prod{(1-q^k)}}{(1-q)^n}$$

Для того, чтобы найти конкретный коэффициент, применяем формулу Коши. Для этого интегрируем $F(q)/q^l$ по единичной окружности (в комплексной плоскости, разумеется) . С помощью замены $q=exp(2ix)$ сводим интеграл к следующему виду

$$\frac{1}{\pi}\int cos(mx) \prod \frac{sin(kx)}{sin(x)}dx, $$

где $m$ вычисляется по $l$ и $n$. Легко выяснить, чему равно $m$ для максимального коэффициента. В зависимости от остатка деления $n$ на 4, $m$ равно 0 или 1. (у меня есть смутное подозрение, что именно это переключение 0 и 1 порождает ту самую 1/2).
Далее, нехитрые оценки для синуса показывают, что основной вклад в интеграл дает область $|x|<\pi / n$. Хорошо видно, как возникает n!.
Для дальнейших оценок уместно вспомнить знаменитую формулу Эйлера для произведения синусов.
Кроме того, переход к половинному углу порождает такое же произведение с косинусами ...
В общем, есть чем заняться:-).

[sup]

Ну что ж ... Похоже верная гипотеза. У меня получилось

$$M(n)=C\frac{n!}{\sqrt{n(n+1)(2n+1)}}(1+O(1/n)).$$

[e7e5]

Спасибо большое sup. Отдельное спасибо за труд И.В. Проскурякова - за прекрасный задачник по Линейной Алгебре. Именно одна из заинтересовавших задач И.В. Проскурякова привела к этому исследованию.

[e7e5]

sup в сообщении #380206 писал(а):

Ну что ж ... Похоже верная гипотеза.

Остается несколько неясных моментов относительно данного факта.
Данный вопрос оказался связан с несколькими разделами математики.

Начнем с простого. 1) Во-первых, интересно все-таки получить комбинаторное доказательство.
2) Во-вторых. связь с векторным пространством.
Известно для $P_n(x)=1(1+x)(1+x+x^2)...(1+x+...+x^{n-1})$ коэффициенты задаются $T(n,k)$, здесь
$T(n+1,k)=T(n,k)+T(n,k-1)+...+T(n,k-n)$, $T(n,k)$ достигает максимума при
$k=n(n-1)/4$.
Получена оценка для $M(n)$ (правда погрешность еще предстоит оценить).

Кроме того, известно, что $T(n,k)$ eсть ранг векторного пространства
$H^k(GL_n/B)$ . Из теоремы "Hard Lefschetz" следует, что $T(n,k)$ является унимодальной последовательностью ( при фиксированном $n$, $k$ меняется).
Как ссылка : Weyl groups,
http://en.wikipedia.org/wiki/Weyl_group

Hard Lefschetz theorem,
http://en.wikipedia.org/wiki/Lefschetz_ ... ne_theorem

Sperner property
http://en.wikipedia.org/wiki/Sperner_pr ... rdered_set
Если есть оценка для $M(n)$, то что это дает для п2? Иные идеи, комментарии, были бы очень интересны.

[e7e5]

Для очень-очень больших чисел ( в духе и смысле работы Эйлера про представление синуса в виде бесконечных произведений),
когда получаются $n-1/2$

какой может это нести смысл математический ?
( а может быть применительно и к физическим объектам, когда при переходе от верхнего уровня к нижнему постоянно вылазит $\pm 1/2$, что-то это напоминает в "большом беспорядке")

[e7e5]

Также известно:
$\left| P\left( \frac{\mathrm{inv}(\pi)-\frac 12{n\choose 2}}{\sqrt{n(n-1)(2n+5)/72}}\leq x\right)-\Phi(x)\right| \leq \frac{C}{\sqrt{n}}$, здесь $\Phi(x)$ - обозначает стандартное нормальное распределение.

Как из этого факта следует, что $M(n+1)/M(n)=n-\frac 12+o(1)$?