по следам перестановочного неравенства

[Sonic86]

Понятно
Руст!
То есть $S(n) \sim a n^4$ и $a$ - трансцендентно?!
И еще: получается Вы строите перестановку (задаете для нее формулу), сумма на которой не минимальна, но минимальна асимптотически? Я правильно понял?

Коэффициенты численно такие: $b = 0,094541578, a=0,059713900$ (Excel).

[Руст]

Sonic86 писал(а):

Понятно
Руст!
То есть $S(n) \sim a n^4$ и $a$ - трансцендентно?!
И еще: получается Вы строите перестановку (задаете для нее формулу), сумма на которой не минимальна, но минимальна асимптотически? Я правильно понял?

Коэффициенты численно такие: $b = 0,094541578,a=0,059713900$ (Excel).

Да, только расчёты с двойной точностью на Си дали $b=0.0945415777.., \ln(\frac 1b -2)=3-9b, a=b-5.5b^2+12b^3-9b^4=0.0548032...$. a выражается от b как многочлен четвёртой степени, я раньше ошибся в этих коэффициентах.

[Sonic86]

Так выглядит распределение $S$ для $n=4$ при всевозможных перестановках

(не получилось вставить диаграмму из Excel - научите )

Для $S=44...100$ значения такие (по порядку):
8 24 24 6 12 6 45 2 24 15 12 45 6 9 12 12 45 9 18 9 6 12 9 9 12 15 30 12 0 8 9 12 15 6 0 6 12 3 2 9 3 12 0 3 0 3 15 0 0 3 0 3 0 3 0 0 1

Что это за распределение?

[Sonic86]

Ура! Мужики! Я прогу написал! Если научусь цитировать, то могу код выложить, на С++. Как и говорил, там тупо m раз локальная оптимизация со случайным поиском, так что значения не точные, а только с вероятностью, только вот не знаю, с какой Я по нескольку сотен испытаний проводил (от 200 до 1000 с ростом n).
$n=1..10$ $S(n)=1; 6; 18; 44; 89; 271; 428; 642; 930$.
$n=11..20$ $S(n)=1304; 1781; 2377; 3111; 4002; 5073; 6345; 7842; 9588; 11610$.
$n=21..30$ $S(n)=13934; 16592; 19613; 23029; 26887; 31179; 35979; 41316; 47223; 53742$.
$n=31..40$ $S(n)=60912; 68776; 77379; 86764; 96979; 108069; 120083; 133075; 147091; 162185$.
$n=41..50$ $S(n)= 178406; 195819; 214472; 234433; 255753; 278496; 302720; 328491; 355878; 384940$.

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

Например, для $n=20$ у меня при 100 испытаниях получилось такое распределение суммы по значениям от 11610 до 11630:
1 4 5 11 11 8 14 6 11 9 8 4 1 0 3 1 1 1 0 1 0
Если 11610 - действительно минимум, то грубо обобщая, можно утверждать, что нескольких сотен испытаний должно хватать. Хотя, конечно, не знаю.
Распределение это, очевидно, не нормальное. Хи-квадрат с этим согласен.

[maxal]

Sonic86, текущие известные значения $S(17)=6344$ и $S(19)=9587$ меньше полученных вами.

[lel0lel]

Для проверки написал прогу близкую к предложенной Sonic86. Сейчас железо помощнее нежели в девятом году - можно сделать больше оптимизаций на случайно сгенерированных данных. Для каждого $17\leqslant n\leqslant 34$ я делал по $20000$ проверок, вот результаты:

{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17},{16,15,11,12,8,13,4,7,5,10,6,3,2,14,9,17,1},{17,13,12,8,10,5,14,7,9,4,6,11,15,2,3,1,16},6344}

{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18},{18,16,10,14,9,11,6,12,4,5,7,13,3,8,2,15,1,17},{17,14,15,8,10,7,11,5,13,9,6,3,12,4,16,2,18,1},7842}

{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19},{19,16,14,12,15,10,5,8,6,9,4,11,3,13,7,17,2,1,18},{18,17,13,11,7,9,15,8,10,6,12,4,14,3,5,2,16,19,1},9587}

{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20},{20,18,16,14,8,9,11,15,10,4,6,5,12,3,7,13,2,17,1,19},{19,17,13,11,15,12,8,5,7,16,9,10,4,14,6,3,18,2,20,1},11610}

{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21},{20,19,15,12,14,17,6,8,13,9,7,5,4,10,16,11,3,2,18,21,1},{21,18,16,15,10,7,17,11,6,8,9,12,13,5,3,4,14,19,2,1,20},13933}

{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22},{22,20,18,14,13,11,12,6,15,5,9,17,7,8,3,10,16,4,2,19,1,21},{21,19,15,14,13,12,10,17,6,16,8,4,9,7,18,5,3,11,20,2,22,1},16592}

{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23},{22,21,19,12,15,14,13,9,17,5,6,11,8,16,4,7,18,3,10,2,20,23,1},{23,20,16,19,12,11,10,13,6,18,14,7,9,4,15,8,3,17,5,21,2,1,22},19612}

{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24},{24,22,20,18,14,16,9,11,6,15,12,17,4,8,7,5,10,19,3,13,2,21,1,23},{23,21,17,14,15,11,16,12,19,7,8,5,20,9,10,13,6,3,18,4,22,2,24,1},23028}

{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25},{25,23,20,21,19,12,11,8,10,13,5,14,15,17,7,9,4,16,6,3,18,2,22,1,24},{24,22,19,14,12,16,15,18,13,9,21,7,6,5,11,8,17,4,10,20,3,23,2,25,1},26871}

{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26},{26,24,22,20,19,14,11,18,12,6,15,5,10,7,8,16,13,4,17,9,21,3,2,23,1,25},{25,23,19,16,14,15,17,9,12,21,8,22,10,13,11,5,6,18,4,7,3,20,24,2,26,1},31178}

{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27},{26,25,22,18,19,14,17,20,9,10,12,15,5,8,6,13,21,16,4,7,23,11,3,2,24,27,1},{27,24,22,20,15,17,12,9,18,14,11,8,23,13,16,7,4,5,19,10,3,6,21,25,2,1,26},35978}

{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28},{28,26,24,22,19,18,12,14,11,15,7,17,6,16,9,20,4,10,21,8,13,3,23,5,2,25,1,27},{27,25,22,18,17,15,19,14,16,11,21,8,20,7,12,5,23,9,4,10,6,24,3,13,26,2,28,1},41315}

{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29},{29,26,25,23,16,17,19,14,11,22,15,10,7,6,13,18,21,8,4,9,12,20,3,24,5,27,2,1,28},{28,27,24,19,22,17,13,16,18,8,11,15,20,21,9,6,5,12,23,10,7,4,25,3,14,2,26,29,1},47223}

{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30},{30,28,26,22,24,18,13,20,11,15,16,7,8,14,9,17,19,12,21,4,23,6,5,10,3,25,2,27,1,29},{29,27,25,22,16,18,21,12,20,13,11,23,19,10,14,7,6,9,5,24,4,15,17,8,26,3,28,2,30,1},53739}

{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31},{30,28,27,24,25,23,16,17,20,10,8,22,13,11,7,15,5,12,19,6,9,14,4,18,21,3,26,29,2,31,1},{31,29,26,22,17,15,19,16,12,21,24,8,13,14,20,9,25,10,6,18,11,7,23,5,4,27,3,2,28,1,30},60910}

{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32},{32,30,28,25,20,23,22,16,13,18,12,14,11,21,7,24,15,5,6,17,10,26,4,8,19,9,3,27,2,29,1,31},{31,29,27,23,24,17,15,19,20,13,18,14,16,8,22,6,9,26,21,7,11,4,25,12,5,10,28,3,30,2,32,1},68776}

{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33},{33,30,28,26,27,20,16,19,13,21,23,8,11,14,12,10,17,24,5,18,15,6,22,7,25,9,4,29,3,31,2,1,32},{32,31,29,25,19,21,23,17,22,12,10,26,18,13,14,16,9,6,27,7,8,20,5,15,4,11,24,3,28,2,30,33,1},77377}

{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34},{34,32,30,28,24,21,25,13,15,20,14,9,19,16,11,22,7,17,10,23,26,18,12,6,4,27,8,5,3,29,2,31,1,33},{33,31,29,25,23,22,16,27,21,14,18,26,11,12,17,8,24,9,15,6,5,7,10,19,28,4,13,20,30,3,32,2,34,1},86763}

[lel0lel]

Приведу улучшенные результаты, может быть пригодятся. Увеличив для каждого $n$ число попыток отыскать оптимальное решение и, помимо $swap(a_i,b_j)$, где $a_i, b_j$ элементы одной перестановки, использовав $swap1(a_i, b_j, c_j, d_k)$, где $a_i, b_i$ и $c_j, d_k$ элементы двух различных перестановок, удалось найти решения у которых $S(22)=16591$, $S(26)=31177$, $S(27)=35976$, $S(28)=41314$, $S(29)=47221$, $S(31)=60908$, $S(32)=68774$, $S(33)=77375$, $S(34)=86762$.

Решения:

(Оффтоп)

{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22},
{22,20,18,16,15,11,8,10,13,5,12,4,7,14,3,17,6,9,2,19,1,21},
{21,19,15,13,11,12,14,10,7,16,6,17,9,4,18,3,8,5,20,2,22,1},16591}
{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26},
{25,24,20,18,19,22,14,11,7,8,15,12,9,13,5,16,4,6,17,21,3,10,2,23,26,1},
{26,23,22,18,14,10,13,15,21,16,8,9,11,7,17,5,19,12,4,3,20,6,24,2,1,25},31177}
{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27},
{26,24,23,20,18,22,12,15,16,11,6,17,8,7,5,10,14,4,19,9,3,13,21,25,2,27,1},
{27,25,21,18,16,11,17,12,10,13,22,7,14,15,19,9,6,20,4,8,23,5,3,2,24,1,26},35976}
{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28},
{27,26,24,21,19,17,16,18,10,8,12,9,14,5,15,20,23,11,4,13,6,3,7,22,2,25,28,1},
{28,25,22,19,17,16,14,11,18,20,12,15,9,23,7,5,4,8,21,6,13,24,10,3,26,2,1,27},41314}
{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29},
{29,26,25,23,21,15,18,10,11,16,20,12,9,6,13,19,8,14,4,22,17,5,3,24,7,27,2,1,28},
{28,27,24,19,17,20,14,22,18,11,8,12,15,21,9,6,13,7,23,4,5,16,25,3,10,2,26,29,1},47221}
{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31},
{30,28,27,22,24,21,14,19,20,9,13,18,15,25,11,7,8,6,16,5,4,12,23,10,17,3,26,29,2,31,1},
{31,29,26,24,18,17,22,14,12,23,15,10,11,6,13,19,16,20,7,21,25,8,4,9,5,27,3,2,28,1,30},60908}
{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32},
{32,30,27,24,26,17,21,14,10,20,16,22,9,12,7,18,8,13,11,23,19,15,4,25,5,6,28,3,2,29,1,31},
{31,29,28,24,18,23,16,21,26,12,13,9,20,14,22,8,17,10,11,5,6,7,25,4,19,15,3,27,30,2,32,1},68774}
{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33},{33,31,29,25,24,22,16,18,13,17,9,19,14,26,21,8,15,12,5,10,20,23,7,27,6,11,4,3,28,2,30,1,32},{32,30,28,25,21,19,23,18,22,15,26,11,14,7,8,20,10,12,27,13,6,5,16,4,17,9,24,29,3,31,2,33,1},77375}
{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34},{34,32,30,27,28,21,16,22,24,13,15,10,18,14,23,12,6,17,8,20,7,25,5,19,11,4,26,9,3,29,2,31,1,33},{33,31,29,26,20,22,25,16,13,21,17,23,12,14,8,15,28,9,18,7,19,5,24,6,10,27,4,11,30,3,32,2,34,1},86762}

[maxal]

Свежий препринт по смежной теме:
On a rearrangement inequality of multiple sequences

[kotenok gav]

В общем, в статье, которую вы привели, по задаче в этом топике есть лишь одна оценка (снизу) - $n(n!)^{\frac3n}$. Она, конечно, дает погрешность лишь около 1% (для $n=17$ - 0.92, для $n=20$ - 1.2), но...

[DeBill]

kotenok gav в сообщении #1471627 писал(а):

в этом топике есть лишь одна оценка (снизу) - $n(n!)^{\frac3n}$.

Ну, и по Стирлингу, будет что-то типа $v_{min}\geqslant \frac{n^4}{e^3}$....
Грубую оценку сверху тож можно получить:
Считая перестановки независимыми, для матожидания суммы будем иметь
$E=n(\frac{n+1}{2})^3 \sim \frac{n^4}{8}$. Так что $v_{min}\sim\leqslant \frac{n^4}{8}$
И в мире, где $e=2$, все бы получилось....