неравенство с количеством инверсий

[maxal]

Несколько задач с возрастающей сложностью.

1) Для всякой перестановки $p$ размера $n$ докажите, что суммарное количество инверсий в перестановках $\overline{p}\circ p^{-1}$ и $p^{-1}$ не меньше $\frac{n(n-1)}2$, причём это значение достигается только если перестановка $p$ тождественная.

Здесь $\overline{p}$ - перестановка, получаемая из $p$ прочтением справа налево - например, $\overline{(2,1,3)}=(3,1,2)$.

[Connector]

Кажется, решил Вашу задачу.
Перестановку $p’$ можно разложить в произведение перестановки $(n,...3,2,1)$ и перестановки $p$. Следовательно, $p’$\circ$p^—{1}$ имеет столько же инверсий, сколько (n,...3,2,1), то есть $n(n-1)/2$. Верность второго Вашего утверждения очевидна, т.к. перестановки $p$ и $p^—{1}$ имеют равное число инверсий.
Кстати, перестановку $(n,...1)$ можно задать аналитически: каждому $i$ она соотносит $n-i+1$.

[maxal]

Connector, идея правильная, но если сформулировать чётче, то получается совсем просто. Действительно, $\overline{p}=(n,n-1,\dots,1)\circ p$, и поэтому $\overline{p}\circ p^{-1}=(n,n-1,\dots,1)\circ p\circ p^{-1}=(n,n-1,\dots,1)$. Таким образом, первая перестановка в данной паре равна $(n,n-1,\dots,1)$, независимо от $p$, и уже в ней количество инверсий равно $\frac{n(n-1)}2$. Вторая перестановка в данной паре, т.е. $p^{-1}$, не дает вклада в количество инверсий только если $p$ тождественная.

Вторая задача:

2) Для всякой перестановки $p$ размера $n$ докажите, что суммарное количество инверсий в перестановках $p$ и $\overline{p}$ равно $\frac{n(n-1)}2$.

[Connector]

Именно это я и пытался выразить, но, действительно, получилось недостаточно отчётливо.
К решению второй задачи: достаточно показать, что всякая пара образует инверсию в $p$ в том и только в том случае, когда не образует инверсии в $p’$. Это можно показать наглядно, рассматривая линейные записи перестановок (которыми мы с Вами пользуемся): пара $(i,j)$ образует инверсию, если $i>j$, но имя $i$ предшествует имени $j$; при прочтении справа налево меняется порядок следования, но не отношение больше/меньше.
Возможно, требуется более строгое доказательство; нужно получше подумать, чтобы обойтись без метасемиозиса. Всякая перестановка определяет на множестве новый порядок; при сравнении двух упорядочений и возникает понятие инверсии...
Вероятно, Вы имели в виду: «перестановки размера $n$».

[Connector]

Другими словами, пара $(a_{i},a_{j})$ образует инверсию, если $a_{i}>a_{j}$ и $j>i$. Но перестановка $p’$ меняет порядок индексов на обратный.