2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2, 3  След.
 
 Перестановки и число инверсий
Сообщение18.09.2010, 10:27 
Известно, что число инверсий в перестановке $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$.

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

 
 
 
 Re: Перестановки
Сообщение18.09.2010, 10:36 
Аватара пользователя
Что значит "число инверсий в перестановке"?

 
 
 
 Re: Перестановки
Сообщение18.09.2010, 10:40 
e7e5 в сообщении #353634 писал(а):
Есть сомнения в правильности рассуждений. Можно ли решать проще?

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

 
 
 
 Re: Перестановки
Сообщение18.09.2010, 10:50 
Профессор Снэйп в сообщении #353639 писал(а):
Что значит "число инверсий в перестановке"?

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

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

 
 
 
 Re: Перестановки
Сообщение18.09.2010, 11:01 
e7e5 в сообщении #353645 писал(а):
Например, перестановка наутральных чисел:
$2,3,5,4,1$
Число инверсий: $4+0+0+1=5$

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

 
 
 
 Re: Перестановки
Сообщение18.09.2010, 11:02 
Аватара пользователя
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$

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

 
 
 
 Re: Перестановки
Сообщение18.09.2010, 11:06 
Имелось в виду количество "неправильных" пар $(i,k)$, т.е. таких $i<k$, что $a_i>a_k$.

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

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

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

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

 
 
 
 Re: Перестановки
Сообщение18.09.2010, 11:35 
e7e5 в сообщении #353657 писал(а):
ewert
Как вам кажется для этой перестановки?

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

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

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

 
 
 
 Re: Перестановки
Сообщение18.09.2010, 11:41 
Аватара пользователя
ewert в сообщении #353673 писал(а):
Ну да, только шибко уж формально.

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

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

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

 
 
 
 Re: Перестановки
Сообщение18.09.2010, 11:49 

(Оффтоп)

Профессор Снэйп в сообщении #353677 писал(а):
Очевидно, что сумма этих чисел равна

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

 
 
 
 Re: Перестановки
Сообщение18.09.2010, 11:52 
ewert в сообщении #353673 писал(а):
Не знаю. Что восемь -- согласен, а вот как Вы считаете -- в упор не понимаю.

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

 
 
 
 Re: Перестановки
Сообщение18.09.2010, 11:53 
ewert
ewert в сообщении #353673 писал(а):
e7e5 в сообщении #353657 писал(а):
ewert
Как вам кажется для этой перестановки?

Не знаю. Что восемь -- согласен, а вот как Вы считаете -- в упор не понимаю.
Вы считаете по $i$, а e7e5 - по $a_k$, если следовать Вашим обозначениям:
ewert в сообщении #353655 писал(а):
Имелось в виду количество "неправильных" пар $(i,k)$, т.е. таких $i<k$, что $a_i>a_k$.

 
 
 
 Re: Перестановки
Сообщение18.09.2010, 12:00 
EtCetera в сообщении #353683 писал(а):
Вы считаете по $j$, а e7e5 - по $a_k$, если следовать Вашим обозначениям

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

 
 
 [ Сообщений: 45 ]  На страницу 1, 2, 3  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group