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

Я определяю общее число инверсий по методу из учебника Ким, Крицков (Алгебра и Аналитическая геометрия). Но не понимаю, как подсчитать инверсии для переменных.

Задание:

$$k, k+1, ..., n, k-1, k-2,..., 2, 1.$$

Спасибо.

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

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

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


9917

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

Все числа здесь разделены на две группы: первая кончается числом $%n$%, и за ней начинается вторая. Пара чисел, образующих инверсию, может относиться либо ко второй группе, где все числа идут в обратном порядке, либо к двум разным группам. Тогда получается инверсия, так как в первой группе, стоящей левее, каждое число больше любого из чисел второй группы. Внутри первой группы инверсий нет: там всё идёт в порядке возрастания.

Число инверсий внутри второй группы равно числу пар (неупорядоченных), а это $%\frac{(k-1)(k-2)}2$%. Пар другого типа имеется $%(n-k+1)(k-1)$% (это перемноженные количества элементов одной и другой групп).

Найденные величины надо сложить, вынося общий множитель $%k-1$% за скобку. Получится $$(k-1)\cdot\left(\frac{k-2}2+n-k+1\right)=(k-1)\cdot\left(n-\frac{k}2\right).$$

ссылка

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

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

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

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

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

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

отмечен:

×50

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

показан
666 раз

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

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

по почте:

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

по RSS:

Ответы

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

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