Высшая Математика Решение задач и примеров - OnLine
./ Главная /Вычисление определителя матрицы, ШАГ-1/Справка/Инверсии >


Language : English

Вычислить определитель матрицы...
Теория определителей...

Инверсии перестановки

Каждая последовательность k различных элементов с учетом порядка называется перестановкой этих элементов. Следовательно, перестановки из k элементов отличаются друг от друга только порядком входящих в них элементов. Например из первых шести чисел натурального ряда можно образовать следующие перестановки :

  1,2,3,4,5,6
  4,6,5,1,3,2
  2,1,6,5,4,3
   . . .
и другие.

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

Например, определим число инверсий в следующей перестановке: (5,3,1,4,2,6).

Решим задачу за пять шагов, на первом шаге выделим первый (слева направо) элемент и подсчитаем число элементов стоящих правее от него меньших чем он сам. (меньшие элементы будем зачеркивать). Затем аналогичным образом обработаем второй элемент и т.д.

  1)   5,3,1,4,2,6   =>  4
  2)   5,3,1,4,2,6   =>  2
  3)   5,3,1,4,2,6   =>  0
  4)   5,3,1,4,2,6   =>  1
  5)   5,3,1,4,2,6   =>  0

Итого, число инверсий в заданной перестановке составляет:  4 + 2 + 0 + 1 + 0 = 7

Перестановка называется четной, если число инверсий в ней четно, и нечетной - в противном случае. В частности, рассмотренная выше перестановка нечетная, так как количество инверсий в ней равно семь.

Теория определителей...
Вычислить определитель матрицы...
к списку решаемых задач...