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

Подстановки. Знак подстановки

Подстановкой степени n называется биективное отображение множества M = { 1; 2; …; n } на себя, где n N.

Подстановку удобно записывать в виде таблицы

(1).

Порядок чисел в первой строке таблицы не является существенным, важно, чтобы для любого k число j (k) было записано непосредственно под k.

Пример 2.1. Записать все подстановки степени три.

.

Число подстановок степени n определяется формулой P _n = n!

Пара { i, k } образует в подстановке инверсию, если i < k, но j (i) > j (k) (разности i - k и j (i)- j (k) имеют разные знаки).

1. Записываем подстановку в виде (1) (первая строка записана в порядке возрастания номеров).

2. Считаем во второй строке количество чисел, предшествующих числу 1 и обозначаем a₁. Зачеркиваем 1.

3. Считаем во второй строке количество чисел, предшествующих числу 2 (не зачеркнутых), обозначаем a₂. Зачеркиваем 2 и т.д.

4. Складываем все полученные числа a₁ + a₂ + … +a _n-1.

Пример 2.2. Подстановка j₁ не имеет инверсий. В подстановках j₂, j₃ одна инверсия; j₄, j₅ - две инверсии; j₆ - три инверсии.

Подстановка называется четной (нечетной), если она содержит четное (нечетное) число инверсий.

	1; если j - четная подстановка -1; если j - нечетная подстановка.

Знак подстановки signj =

Дата добавления: 2014-10-22