Здравствуйте!

Задание:

В перестановке $%a_1, a_2,..., a_{n-1}, a_n$% имеется P инверсий. Сколько инверсий будет в перестановке $%a_n,a_{n-1},..., a_2, a_1 $%?

Спасибо.

задан 8 Сен '14 19:28

изменен 8 Сен '14 21:54

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

10|600 символов нужно символов осталось
1

Два различных числа образуют инверсию в первой перестановке тогда и только тогда, когда они не образуют инверсию во второй перестановке. Тогда на каждую неупорядоченную пару, которых всего имеется $%\frac{n(n-1)}2$%, приходится ровно одна инверсия из общего количества. Именно таково и будет суммарное количество инверсий. Поэтому ответом будет $%\frac{n(n-1)}2-P$%.

ссылка

отвечен 8 Сен '14 21:51

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×50

задан
8 Сен '14 19:28

показан
324 раза

обновлен
8 Сен '14 21:51

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru