3214

3241

4123

4132

4321

Рис. 1. Усеченный октаэдр, на котором показано изменение числа инверсий, когда меняются местами два соседних элемента перестановки.

1 1 п п - 1

• + Y = Я„.

.Аналогичным способом легко получить и соответствующую производяпдую функцию.

Ясно, что если поменять местами соседние элементы перестановки, то общее число инверсий увеличится или уменьшится на единицу. На рис. 1 показаны 24 перестановки множества {1,2,3,4}; линиями соединены перестановки, отличающиеся одна от другой положением двух соседних элементов; двигаясь вдоль линии вниз, мы увеличиваем число инверсий на единицу. Следовательно, число инверсий в перестановке тг равно длине нисходящего пути из 1234 в тг на рис. 1; все такие пути должны иметь одинаковую длину.

Заметим, что эту диаграмму можно рассматривать как трехмерное твердое тело - "усеченный октаэдр" имеющий 8 шестиугольных и 6 квадратных граней. Это один из классических правильных многогранников, которые исследовал еще Архимед (см. упр. 10).

Не следует путать "инверсии" перестановок (inversions of а permutation) с обратными перестановками {inverse of а permutation). Вспомним, что перестановку можно записывать в виде двух строк:

«2

3 аз

п а„

Обратной назьшается перестановка aj ... а, которая получается, если в (4) поменять местами строки, а затем упорядочить столбцы в порядке возрастания по верхним элементам:

a2 2

аз 3

Например, обратной к перестановке 59182С473 будет перестановка 359716842, так как

591826473N 12345678 9

/12345678 9\ 359716842

Можно дать другое определение обратной перестановки: о! = к тогда и только тогда, когда - j.

Понятие обратной перестановки впервые ввел X. А. Роте (Н. А. Rothe) [в Samm-lung combinatorisch-analytischer Abhandlungen, edited by K. F. Hindenburg, 2 (Leipzig, 1800), 263-305]. Oh за.метил интересную связь между обратными перестановками и инверсиями: обратная перестановка содержит ровно столько инверсий, сколько походная. Роте дал не са.мое простое доказательство этого факта, но оно поучительно и притом довольно красиво. Построим таблицу размером n х п, наподобие шахматной доски, в которой точки стоят в j-n клетке г-й строки, если щ = j. После этого расставим крестики во всех клетках, снизу от которых (в том же столбце) и справа (в тон же строке) есть точки. Например, для 591826473 диаграмма будет выглядеть следующим образом:

Количество крестиков равно числу инверсий, так как нетрудно видеть, что bj равно числу крестиков в j-м столбце. Если мы теперь транспонируем диагра.\1му (поменяв ролями строки и столбцы), то получим диаграмму для обратной по отношению к исходной перестановки; значит, число крестиков (число инверсий) одинаково в обоих случаях. Роте использовал данный факт для доказательства того, что детерминант матрицы не меняется при транспонировании.

Для анализа некоторых алгоритмов сортировки необходимо знать число перестановок 71 элементов, содержащих ровно к инверсий. Обозначим это число через 1„{к): в табл. 1 приведено несколько первых значений данной функции.

Из таблицы инверсий Ь] 6-2 • Ьп ясно, что 7„(0) = 1, /„(1) = n - 1 и что выполняется свойство симметрии:

1п{г)-к)=1п{к).

Далее, так как значения Ьк можно выбирать независимо одно от другого, нетрудно видеть, что производящая функция

Gn{z) = 1„{0) + In{l)z + In{2)z + (7)

Таблица 1

перестановка с к инверсиями

удовлетворяет соотношению G„(z) = (1 + z + •••-!- )G„ i(z); следовательно, она имеет довольно простой вид, как показано О. Родригесом (О. Rodrigues) [J. de Math. 4 (1839), 236-240]:

{1 + Z + --- + z-)... (1 + z){l) = (1 - z")... (1 - z2)(l - z)l{l - zT. (8)

С помощью этой производящей функции можно легко продолжить табл. 1 и убедиться, что числа, расположенные под ступенчатой линией в таблице, удовлетворяют соотношению

/„(А;) =/„(А;-l) + /„ i(A;), где к<п. (9)

(Для чисел, находящихся над ступенчатой линией, это соотношение не выполняется.) Более сложные рассуждения (см. упр. 14) показывают, что на самом деле справедливы формулы

/п(2) /„(3) /п(4) /„(5)

("Г)-а) г:угл

("Г)-("Г)-.

n > 2; n > 3; n > 4; n > 5.

Общая формула для /„(А;) содержит около 1.6\/fc слагаемых:

/гг + А;-2

+ (-1)

/n + Jfc-3\ Jfc-2

гг-ьА;-6 Jfc-5

/гг-ЬА:-8 А:-7

(n-\-k - Uj - \\ fn + k - Uj-j - 1 \\ k-Uj ) V k-Uj-j

п>к, (10)

где Uj - (3j - i)/2 - так называемое "пентагональное число"

Разделив G„(z) на п!, получим производяшую функцию Qniz) распределения вероятностей числа инверсий в случайной перестановке п элементов. Она равна произведению

gniz)hi{z)h2{z)...hn{z), (И)