где hk{z) = (1 + z + • • • + z)/k - производящая функция равномерного распределения случайной величины, принимающей целые неотрицательные значения, меньшие к. Отсюда*

шеап(р„) = mean(/ii) + mean(/?,2) + + mean(/i„)

= 0 + 1 (12)

var(p„) = var(/?,i) + var(/i2) ++ var(/i„)

= 0 + 1 iiiji .liMi, ,13)

Таким образом, среднее число инверсий довольно велико - около \п; стандартное отклонение также весьма велико - около гг/.

В качестве интересного завершения данной темы рассмотрим одно замечательное открытие, принадлежащее П. А. Мак-Магону (Р. А. MacMahon) [Атег. J. Math. 35 (1913), 281-322]. Определим индекс перестановки О] ао.. .а„ как сумму всех j, таких, что aj > o+i, 1 < j < п. Например, индекс перестановки 591826473равен 2-ь4-ь6-ь8 = 20. Индекс случайно совпал с числом инверсий. Если составить список всех приведенных ниже 24 перестановок множества {1,2,3,4}, то получится, что число перестановок, имеющих данный индекс к, равно числу перестановок, имеющих к инверсий.

Количество Количество

Перестановка Индекс инверсий Перестановка Индекс инверсий

1234 О О 3124 1 2

12 43 3 1 3142 4 3 132 4 2 1 3214 3 3

13 42 3 2 32 41 4 4 142 3 2 2 3 412 2 4 1432 5 3 3 4i2l 5 5

2134 1 1 4il23 1 3

2143 4 2 4132 4 4

2 31 4 2 2 4213 3 4

2 3 41 3 3 42 31 4 5

2 41 3 2 3 43il2 3 5

2 431 5 4 4321 6 6

На первый взгляд, этот факт может показаться почти очевидным, однако после некоторых размышлений он начинает казаться чуть ли не мистическим, и не видно никакого простого прямого его доказательства. Мак-Магон нашел следующее остроумное косвенное доказательство. Пусть ind(ai аг ... а) - индекс перестановки ai 02 ... а„ и соответствующая производящая функция есть

ff„(z) = z"<""=-°">, (14)

* Здесь и далее mean(g) означает среднее значение случайной величины д, а \аг{д) - дисперсию величины д. - Прим. перев.

где сумма в (14) берется по всем перестановкам множества {1,2,... ,п}. Требуется доказать, что Hn{z) = Gn{z)- Для этого определим взаимно однозначное соответствие между гг-мерными строками {qiq-i, тЧп) неотрицательных целых чисел, с одной стороны, и упорядоченными парами п-мерных строк

((«1, «2, ..., а„), (pi ,Р2, • • • ,Рп)) ,

с другой стороны, где ai «2 ... а„ - суть перестановка множества индексов {1,2,..., и Pi > Р2 > • > Рп > 0. Это соответствие будет удовлетворять условию

q\+ 42 ++ Чп= ind(ai а2 ... an) + {р\ + Р2 + + Рп)- (15)

Производящая функция z"""""""", где сумма берется по всем п-мерным стро-ка.\1 неотрицательных целых чисел {qi,q2, , Чп), равна Qn{z) = 1/(1 - z)"; а производящая функция z"\ где сумма берется по всем п-мерным строкам целых чисел (pi,p2, • • ,Рп), таких, что pi > рг > • • > Р»г > О, равна

P„(z) = l/(l-z)(l-z2)...(l-z«), (16)

как показано в упр. 15. Существование взаимно однозначного соответствия, которое удовлетворяет условию (15) и которое мы собираемся установить, доказывает равенство Q„(z) = Hn{z)Pn{z), т. е.

Hn{z) = Q„(z)/P„(z). (17)

Но Qn{z)/Pn{z) и есть Gn{z), как следует из (8).

Требуемое соответствие определяется с помощью простой процедуры сортировки. Любая гг-мерная строка {qi,q2, -.Чп) может быть устойчиво реорганизована в порядке невозрастания > > "" > 9оп5 где 0102... а„ - перестановка, такая, что qa = ga+i и подразумевает aj < aj+j. Установим (pi,p2, • • ,Рп) = (9ai: 9а25 • • ч 9о„) и затем для 1 < j < n вычтем 1 из каждого pi, pj для таких j, которые соответствуют aj > aj+i. По-прежнему pi > р2 > • > Рп, поскольку Pj обязательно превышает Pj+i, если только aj > aj+i. Полученная в результате пара ((ai,аг,... ,а„), (pi,p2, ••• ,Рп)) удовлетворяет условию (15), поскольку суммарное уменьшение элементов р равно ind(ai «2 .. .Яп)- Например, если п = 9 и {qi,...,qg) = (3,1,4,1,5,9,2,6,5), то получим ai...a<) = 685931724и (Р1,...,Р9) = (5,2,2,2,2,2,1,1,1).

Несложно вернуться к {qi,q2; ,qn), когда заданы ai 02 •..а„ и (pi,рг, • • •,Рп) (см. упр. 17). Итак, желае.мое соответствие установлено, теорема Мак-Магона об индексах доказана.

Д. Фоата (D. Foata) и М. П. Шуценберже (М. Р. Schiitzenberger) отыскали неожиданное расширение теоремы Мак-Магона через 65 лет после его первой публикации. Число перестановок п элементов, которые имеют к инверсий и индекс I, равно числу перестановок, которые имеют I инверсий и индекс к. Фактически Фоата и Шуценберже нашли простое однозначное соответствие между перестановками первого и второго типов (см. упр. 25).

УПРАЖНЕНИЯ

1. [10] Какова таблица инверсий для перестановки 2 71845936? Какой перестановке Соответствует таблица инверсий 5012120 0?

2. [М20] Классическая задача Иосифа формулируется следующим образом (см. также упр. 1.3.2-22): п рабов вначале стоят по кругу; после того как т-го раба казнят, круг смыкается, затем опять казнят т-го раба и так до тех пор, пока всех рабов не постигнет эта печальная участь. Таким образом, порядок, в котором рабы подвергаются наказанию, представляет собой перестановку множества {1, 2,..., п}. Например, если п = 8 и m = 4, порядок будет иметь вид 54613872 (первым казнили 5-го раба и т. д.); таблица инверсий для этой перестановки имеет вид 36310010.

Найдите простое рекуррентное соотношение для элементов 6i Ьг ... Ь„ таблицы инверсий в общей задаче Иосифа для п рабов, если каждого т-го раба казнят.

3. [18] Пусть перестановке ах а2 - йп соответствует таблица инверсий bi Ьг ... fcn- Какой перестановке oi ог ... о„ соответствует таблица инверсий

(n-l-bi)(n-2-b2)...(0-b„)?

► 4. [20] Придумайте пригодный для компьютерной реализации алгоритм, который по данной таблице инверсий b\b2...bn, удовлетворяющей условиям (3), строил бы соответствующую перестановку ai а2 an- [Указание. Вспомните методы работы со связями в памяти.]

5. [35] Для выполнения алгоритма из упр. 4 на типичном компьютере потребуется время, приблизительно пропорциональное n+bi-\-----hfcn, а это в среднем равно 0(гг). Можно

ли создать алгоритм, порядок времени выполнения которого был бы существенно меньше, чем п?

► 6. [26] Придумайте алгоритм вычисления таблицы инверсий bi62...b„, соответствующей данной перестановке ai аг •. а„ множества {1,2, ...,п}, время работы которого на типичном компьютере было бы порядка п log п.

7. [20] Помимо таблицы fci Ьг •.. Ьп, определенной в этом упражнении, можно определить некоторые типы таблиц инверсий, соответствующих данной перестановке aia2 ...а„ множества {1, 2,..., п}. В этом упражнении мы рассмотрим три других типа таблиц инверсий, которые возникают в приложениях.

Пусть Cj - число инверсий, первая компонента которых равна j, т. е. число элементов, меньших j и расположенных правее j. [Перестановке (1) соответствует таблица 0 0014 2 15 7; ясно, что О < Cj < j.] Пусть Bj = baj и Cj = Са.

Покажите, что при 1 < j < п справедливы неравенства О < Bj < j и Q < Cj < п - j; покажите также, что перестановку ai а2 .. .an можно однозначно определить, если задана таблица ci сг . с„ или В\ В2 .. В„, или Ci Сг • С„.

8. [М24] Сохраним обозначения, принятые в упр. 7. Пусть aia2...an - перестановка, обратная к ai аг • . an, и пусть соответствующие ей таблицы инверсий - Ъ\ Ьг ... fc, cl (2 сп, Bl В2 .. Вп я С[ С2 . Сп. Найдите как можно больше интересных соотношений между числами aj, bj, Cj, Bj, Cj, a,, bj, Cj, Bj, C].

► 9. [M21] Докажите, что в обозначениях, принятых в упр. 7, перестановка aia2...an представляет собой инволюцию (т. е. обратна самой себе) тогда и только тогда, когда bj = Cj при 1 < j <п.

10. [НМ20] Рассмотрите представленный на рис. 1 октаэдр как многогранник в трехмерном пространстве. Чему равен диаметр усеченного октаэдра (расстояние между вершинами 1234 и 4321), если все ребра имеют единичную длину?

11. [М25] Если 7г = а 1 02 ... an представляет собой перестановку множества {1, 2,. >., п}, то обозначим как

£(7г) = {{ai,aj) \ i<i,ai> aj]

множество ее инверсий, а как