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

[maxal]

Пусть $S_n$ - это множество всех перестановок чисел $\{1,2,\dots,n\}$.
Найдите значение

$$\min_{\pi,\sigma,\tau\in S_n} \sum_{j=1}^n \pi(j)\cdot \sigma(j)\cdot\tau(j)$$

как функцию от $n$.

[Хорхе]

Могу посчитать максимум

[Утундрий]

Просто напросто ничего не понял в обозначениях.

[maxal]

Утундрий
см. что такое перестановка в википедии.
если непонятно обозначение с минимумом, то словесное описание такое: для заданного $n$ нужно выбрать три перестановки $\pi$, $\sigma$ и $\tau$ порядка $n$ так, чтобы указанная сумма была минимально возможной. Нужно выразить это минимальное возможное значение как функцию от $n$.

[Утундрий]

Непонятно обозначение с суммой. Если точкой обозначена композиция, то получается, что Вы там перестановки суммируете, что ли? И кто такой индекс $j$ ? По какому принципу отбираются тройки элементов симметрической груммы, входящие в сумму?

[maxal]

Точка - это обычное произведение. Индекс $j$ бежит от 1 до $n$, для каждого $j$ берется произведение $j$-х элементов всех трех перестановок, и все это суммируется.

[Sinus]

Для случая двух постановок нетрудно показать, что искомый максимум достигается, когда соответствующие подстановки совпадают.

Наверное, этот же результат верен, когда подстановки три (и, соответственно, искомый максимум равен сумме кубов первых n натуральных чисел), только выкладки могут быть несколько длиннее.

[maxal]

Sinus
Результат о двух перестановках - это и есть перестановочное неравенство. Из него легко следует решение для аналогичной задачи с максимумом.
Но в этой спрашивается про минимум.

[Sinus]

Извиняюсь за свою невнимательность...

Опять же, для двух перестановок минимум достигается когда их (перестановок) сумма постоянна и равна n+1. Однако для данной задачи не видно как реализовать такие идеи.

Интересная задача.

[Руст]

Задачу на максимум maxal не стал бы задавать. Для любого количества произведений максимум достигается на тождественных перестановках, соответственно для 3-х сумма кубов равно $S_{max}=\frac{n^2(n+1)^2}{4}$.
Пусть $n=3k, \tau(i)=i, \pi(i)=2k+1-i,i\le k,$
$\pi(i)=i+k,k<i\le 2k,\pi(i)=n+1-i,i>2k, \sigma(i)=\pi^2(i)$.
Тогда $S=3\sum_{i=1}^k i(2k+1-i)(3k+1-i)=\frac{n(n+3)(19n^2+45n+18)}{4*81}$.
Если $n=3k+1$ сделаем неподвижную точку в интервале [k+1,2k+1] в остальном определим так же.Т.е. $\tau(i)=i,\pi(i)=2k+2-i,i\le k+1,$
$\pi(i)=k+i,k+1<i<2k+2,\pi(i)=i+k,i\ge 2k+2,\sigma(i)=\pi^2(i)$.
Тогда $S=(k+1)^3+3\sum_{i=1}^k i(2k+2-i)(3k+2-i)=(k+1)^3+\frac{k(k+1)}{4}[19k^2+37k+16]$.
В случае $n=3k+2$ надо брать две неподвижные точки и определить $\tau(i)=i,\pi(i)=2k+2-i,i\le k+1$
$\pi(i)=i+k+1,k+1<i<2k+2,\pi(2k+2)=2k+2, \pi(i)=3k+3-i,i>2k+2$
$\sigma(i)=\pi^(i),i\not =k+1,2k+2,\sigma(2k+2)=k+1,\sigma(k+1)=2k+2.$
Вроде на них достигается минимум.

[maxal]

Руст
Твои формулы начинают врать с $n=7$. Для $n=7$ минимум равен 271, а у тебя получается 276.

[Руст]

А для случая $n=3k$ правильны?.

[maxal]

Руст
Для $n=3k$ тоже начинаются проблемы, начиная с $n=9$ (у тебя получается 654, а должно быть 642).

[Руст]

Я привлекал только интуитивные соображения для минимизации. Похоже хорошей формулы для минимального значения не существует.

[Руст]

Приведу соображения, приводящие к вышеуказанным формулам.
Введём метрику в группе перестановок $s(n)$: $ro (sigma,sigma')=||\sigma^{-1}\sigma'||$, где норма равно $||\sigma||=\sum_i (l_i-1),\sigma=(x_1,...,x_{l_1})(x_{m_1+1},...,x_{m_2}),...$
$m_1=l_1,m_{i}=m_{i-1}+l_i$. Соответственно расстояние между $\sigma,\sigma'$ равно 1, если найдётся i,j, что $\sigma'(k)=\sigma(k),k\not =i,j, \sigma'(i)=\sigma(j),\sigma'(j)=\sigma(i)$.

$$S(\pi,\sigma,\tau)=\sum_{j=1}^n\pi(j)\sigma(j)\tau(j)$$

принимает локальный минимум, если

$$S(\pi',\sigma',\tau')>S(\pi,\sigma,\tau)$$

для любых перестановок с условием $ro(\pi,\pi')+ro(\sigma,\sigma')+ro(\tau,\tau')=1$.
Указанные перестановки дают локальный минимум.