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

[e7e5]

Известно, что число инверсий в перестановке $a_1, a_2, ... , a_{n-1}, a_n$ равно $k$.
Сколько инверсий будет будет в перестановке
$a_n, a_{n-1}, ..., a_2, a_1$?

Начал с того, что можно определить число инверсий в перестановке индексов
$1, 2, ..., n$, которая получается при замене заданной перестановки на исходное расположение.
Если имеется перестановка чисел $1, 2, ..., n$, то максимальное число инверсий будет равно $\frac {n(n-1)} {2}$. Поскольку по условию задачи число инверсий равно $k$, то в исходной перестановке число инверсий будет
$\frac {n(n-1)} {2} -k$.

Есть сомнения в правильности рассуждений. Можно ли решать проще?

[Профессор Снэйп]

Что значит "число инверсий в перестановке"?

[ewert]

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

Есть сомнения в правильности рассуждений. Можно ли решать проще?

Не знаю, проще ли это будет или нет, но я бы сказал так. При переворачивании каждая инверсия перейдёт в неинверсию и наоборот, откуда и ответ. И слова "максимальное число инверсий" заменил бы на просто "количество пар".

[e7e5]

Профессор Снэйп в сообщении #353639 писал(а):

Что значит "число инверсий в перестановке"?

Всякое расположение чисел $1, 2, ..., n$ называют перестановкой из $n$ чисел. Числа можно заменить символами, обозначить по другому.
Если числа $1, 2, 3, ..., n$ переставить местами ( как-то), то образуется беспорядок или, числа $i$ и $j$, стоящие в перестановке, составляют инверсию, если ( $i>j$).
Вот и считают, какой беспорядок, число инверсий.

Например, перестановка наутральных чисел:
$2,3,5,4,1$
Число инверсий: $4+0+0+1=5$

[ewert]

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

Например, перестановка наутральных чисел:
$2,3,5,4,1$
Число инверсий: $4+0+0+1=5$

А мне чего-то кажется, что $1+1+2+1=5$

[Профессор Снэйп]

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

Профессор Снэйп в сообщении #353639 писал(а):

Что значит "число инверсий в перестановке"?

Всякое расположение чисел $1, 2, ..., n$ называют перестановкой из $n$ чисел. Числа можно заменить символами, обозначить по другому.
Если числа $1, 2, 3, ..., n$ переставить местами ( как-то), то образуется беспорядок или, числа $i$ и $j$, стоящие в перестановке, составляют инверсию, если ( $i>j$).
Вот и считают, какой беспорядок, число инверсий.

Например, перестановка наутральных чисел:
$2,3,5,4,1$
Число инверсий: $4+0+0+1=5$

Ничего не понял! Набор слов вижу, смысла не улавливаю.

[ewert]

Имелось в виду количество "неправильных" пар $(i,k)$, т.е. таких $i<k$, что $a_i>a_k$.

[e7e5]

Вот еще перестановка:
$6, 3, 1, 2, 5, 4$
Число инверсий: $2+2+1+2+1=8$

-- Сб сен 18, 2010 12:11:35 --

ewert
Как вам кажется для этой перестановки?

[Профессор Снэйп]

То есть для $\sigma \in S_n$ инверсией называется такая пара $\langle i,j \rangle \in \{ 1, \ldots, n \}^2$, что $i < j$ и $\sigma(i) > \sigma(j)$. Так?

[ewert]

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

ewert
Как вам кажется для этой перестановки?

Не знаю. Что восемь -- согласен, а вот как Вы считаете -- в упор не понимаю.

Профессор Снэйп в сообщении #353662 писал(а):

То есть для $\sigma \in S_n$ инверсией называется такая пара $\langle i,j \rangle \in \{ 1, \ldots, n \}^2$, что $i < j$ и $\sigma(i) > \sigma(j)$. Так?

Ну да, только шибко уж формально.

[Профессор Снэйп]

ewert в сообщении #353673 писал(а):

Ну да, только шибко уж формально.

Да мы вроде математикой занимаемся, а не чем попало

А в задаче спрашивается, как выражается число инверсий перестановки $\tau(i) = \sigma(n - i + 1)$ через число инверсий перестановки $\sigma$. Очевидно, что сумма этих чисел равна $n(n-1)/2$.

Грамотные определения и обозначения --- три четверти успеха в решении задачи!!!

[ewert]

(Оффтоп)

Профессор Снэйп в сообщении #353677 писал(а):

Очевидно, что сумма этих чисел равна

Нет, а Вы всё-таки аккуратно выпишите, почему это очевидно. Мы ж вроде математикой занимаемся, а не чем попало!

[e7e5]

ewert в сообщении #353673 писал(а):

Не знаю. Что восемь -- согласен, а вот как Вы считаете -- в упор не понимаю.

Еще одна перестановка:
$7, 5, 6, 4, 1, 3, 2$
Число инверсий: $4+5+4+3+1+1=18$

[EtCetera]

ewert

ewert в сообщении #353673 писал(а):

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

ewert
Как вам кажется для этой перестановки?

Не знаю. Что восемь -- согласен, а вот как Вы считаете -- в упор не понимаю.

Вы считаете по $i$, а e7e5 - по $a_k$, если следовать Вашим обозначениям:

ewert в сообщении #353655 писал(а):

Имелось в виду количество "неправильных" пар $(i,k)$, т.е. таких $i<k$, что $a_i>a_k$.

[ewert]

EtCetera в сообщении #353683 писал(а):

Вы считаете по $j$, а e7e5 - по $a_k$, если следовать Вашим обозначениям

Да, так сходится. Мне этот способ даже и в голову не приходил, ибо он алгоритмически явно неэффективен -- поди ещё опознай эти $a_k$, а потом ещё и попропускай лишние.