22. (а) Расставьте числа {1,2,...,п} по кругу, как на циферблате часов, и установите указатель на 1. Затем для j = п, п-1, ..., 1 (именно в этом порядке) передвигайте указатель против часовой стрелки hj + 1 шагов, удаляя из круга те числа, на которые он указывает, и назовите их Oj.

(b) Каждое i подсчитывается так часто, как "замыкается" последовательность Oi Ui+i... а„; это и будет число случаев, когда aj > Oj+i при j > i. Таким образом, каждое j при Oj > Oj+i соответствует подсчитанным однократно индексам 1, ..., j. [Guo-Niu Han, Advances in Math. 105 (1994), 28-29; тот же результат получен и Роулингсом (Rawlings) в контексте следующего упражнения.]

23. Предположим, например, что п = 5 и 0102030405 = 31425. Тогда число холостых выстрелов перед каждым смертельным должно быть 2 + 5fci, 2 + 42, 1 + Зз, 1+22, где kj - некоторое неотрицательное целое. Обратите внимание, что дуальной перестановке 14 2 5 3 соответствует /г-таблица 0112 2 в обозначениях предыдущего упражнения. В общем случае вероятность серии oi 02 ... Оп будет равна

е (9?"+"=Vi)(92"-"*""P2). •. (9+=>n)

1 - gi 1-92 1 -9" л„ л„

Ч1 Ч2 • • • 9n 1

1-9Г 1-9Г "l-A

где Pj = 1 - Qj - вероятность фатального исхода после предыдущих j-1 роковых выстрелов и hih2 ... h„ соответствует двойственной последовательности Oi 02 ... Оп. В частности, при pi = -.-=p„=p = l- g получим вероятность q"""/Gn{q)- Таким образом, будет порядок п ... 2 1. [J. Treadway, D. Rawlings, Math. Mag. 67 (1994), 345-354; Роулингс обобщил этот результат для перестановок мультимножеств в Int. J. Math. &с Math. Sci. 15 (1992), 291-312.]

24. Пусть Оо = 0. Будем говорить, что обобщенный спуск возникает при j < п, если Oj > t(oj+i). После вставки п между Oj-i и Oj появляется новый обобщенный спуск тогда и только тогда, когда Oj-i < t{aj) < п. Предположим, что это произошло, когда j имело значение ji > j2 > • • > jk > 0; пусть другое значение j будет j„ > jn-i > • > jk+i-Тогда jn = п и можно показать, что обобщенный индекс увеличивается на п - fc, когда п вставлено именно перед Oj. [Особый случай, при котором t{j) = j+d для некоторых d > О, рассмотрен Д. Роулингсом, J. Combinatorial Theory А31 (1981), 175-183; он обобщил его на перестановку мультимножеств в работе Linear and Multilinear Algebra 10 (1981), 253-260.

В этом упражнении определено п! различных статистик перестановок, каждая из которых имеет производяшую функцию Gn{z}, выведенную в (7) и (8). Можно определить и значительно больше таких статистик, обобщив формулировку задачи о русской рулетке следующим образом: после j - 1 рокового выстрела новый круг начинается с участника /j(oi,..., Oj i), где fj - произвольная функция, принимающая значения на {1,...,п} \ {oi,..., Oj i}. [См. Guo-Niu Han, CaicuJ Denertien (Thesis, Univ. Strasbourg, 1992), Part 1.3, §7.]

25. (a) Если oi < a„, то h{a) имеет ровно столько же инверсий, сколько а, так как элементы в Oj теперь инвертировали Xj вместо Оп. Но, если oi > о„, h{a) имеет на п - 1 инверсий меньше, поскольку Xj теряет свою инверсию о„ и инверсию каждого элемента в Oj. Таким образом, если положить а;„ = Оп и рекурсивно переобозначить xi.. .Xn-i = f(h{a)), то перестановка /(а) = xi...x„ будет обладать желаемыми свойствами. Получится/(198263745) = 912638745 и /-(l98263745) = 192687345.

(b) Здесь ключевыми являются соотношения inv(a) = inv(a~) и ind(a~) = ind(/(a)~), если а~ есть инверсия а. Таким образом, если аi = а~, 02 = /(Qi), Q3 = Q4 =/"(з) и as = а4 , получим

inv(a5) = тч{а) = тй{аз) = ind(a2 ) = ind(ai ) = ind(a); ind(a5) = ind(aj) = md(a3 ) = ind(a2) = inv(ai) = inv(a). [Math. Nachrichten 83 (1978), 143-159.]

26. (Решение предложено Дороном Зильбергером (Doron Zeilberger).) Среднее от inv(a) md(a) равно

e e e [«i>° [a,>a,+i],

a l<j<k<n l<l<n

что представляет собой полином от п степени, меньшей или равной 4. Вычисление этой суммы для 1 < п < 5 дает соответственно значения О, j, , , ; таким образом, полином имеет вид п(п - 1) + Yenin - 1). После вычитания mean(gn) и деления на var(g„) получим ответ: 9/(2ti + 5) для п > 2, если исходить из (12) и (13).

27. Рассматривая дп ... дг gi как перестановку мультимножества, получим inv(ai ai.. .an) = inv(g„ .. .дг gi) (см. раздел 5.1.2). Отсюда, используя обозначения из ответа к упр. 16 и результаты упр. 5.1.2-16, получим

Enjal, z) inv(a,...a„) ind(oi...a„) Pl+--+P„

(1-г)...(1-2") " 4-

inv(5„...92 91)91+92+--+9П

= e

91.92.....9n>0

= п!.[."]ПП1 ..

В результате имеем элегантное тождество

ГТ 1 у- Hniw,z)u

1 - wizu V (1 - - w) • (1 - w")(l - г)(1 - г2)... (1 - 2")

из которого и появляется требуемая производящая функция Hniw, z) = u;nd(a )md(a)

(последняя получена Д. П. Розелем (D. Р. Roselle) в Ргос. Amer. Math. Soc. 45 (1974), 144-150). В упр. 25 показано, что та же функция двух переменных подсчитывает индексы и инверсии. Приведенное здесь доказательство принадлежит Гарсиа (Garsia) и Гесселю (Gessel) [см. Advances in Math. 31 (1979), 288-305], которые стремились получить существенно более общий результат.

Если в упр. 4.7-27 положить m = оо, то придем к рекуррентному соотношению

l-z-)jHn-kiw,Z).

"j = l

28. Взаимная замена двух соответствующих элементов изменяет значение суммарного смещения на величину О или ±2; следовательно, суммарное смещение td(ai 02... а„) < 2 inv(ai 02 ... а„).

Hniw,z) = Е() "- - "-))я„-.(«,

Можно также доказать, что td(ai аг . •. а„) > mv(ai аг ... а„). Предположим, что j - наименьший элемент, который находится не на своем месте, и Пк = j. Пусть I будет максимальным, причем I < к и ai > к. Взаимный обмен а; и ак уменьшает количество инверсий на 2{к - I) - 1, а суммарное смещение - на 2{к - I). Таким образом, если для сортировки данной перестановки ai ог ... а„ требуется т повторений этого алгоритма, получим td(oi аг ... а„) = inv(ai аг •.. а„) + т.

Замечание. Среднее суммарное смещение случайной перестановки равно (п - 1)/3 (см. упр. 5.2.1-7). Производящая функция для среднего суммарного смещения не имеет простой формы.

29. Можно получить тг как произведение inv(7r) операций транспонирования г,, где операция Tj меняет местами j и j + 1. Например, путь 1234 1324 1342 3142 на рис. 1 соответствует гг, затем - гз, затем - п; следовательно, 3142 = Г1гзгг. Таким образом, можно получить тгтг из тг, выполнив inv(7r) операций транспонирования, каждая из которых изменит количество инверсий на ±1. Отсюда следует, что 1пу(7Г7г) < inv(7r) + inv(7r). Если имеется равенство, каждое транспонирование добавляет одну инверсию, т. е. Е(пп) D Е{п).

Значит, если Е{пп) D Е(п), нам нужно показать, что некоторая последовательность из £(7Г7г) - £(7г) = inv(7r7r) - ту(7г) операций транспонирования преобразует тг в тгтг. Данные операции транспонирования определяют тт. Этим доказывается справедливость соотношения inv(7r) < 1пу(7Г7г) - inv(7r); следовательно, должно соблюдаться равенство. Предположим, что7г=314592687и E{-ktv) Э E{tv). Если Е{тпт) не содержит (4,1) или (5,4), или (9,5), или (6,2), или (8,6), то тгтг должно быть равно тг. В противном случае Е{пп) содержит одно из них, скажем, (9,5); тогда Е{пп) включает Е{т4п) = Е{31495268 7). Подобным образом по индукции можно доказать справедливость указанного в условиях соотношения для £(7Г7Г) - £(7г).

РАЗДЕЛ 5.1.2

1. Не верно, поскольку оставлен без внимания один важный нюанс. Тот, кто ответил "верно" возможно, забыл (или не знает) данное в разделе 4.6.3 определение операции Mi U Мг, согласно которому Mi U Мг является множеством только в том случае, если Mi и Мг также являются множествами. На самом деле а т/З - перестановка Mi И Мг.

2. bcaddadadb.

3. Разумеется, нет, поскольку может быть и а = /3. (Однако теорема о единственности разложения показывает, что такие случаи встречаются не часто.)

4. (d) т (6 с d) т (6 Ь с а d) т (Ь а 6 с d) т (d).

5. Число вхождений пары ... хх... равно числу столбцов J либо на единицу меньше. Если х - наименьший элемент, то эти числа равны тогда и только тогда, когда х - не первый элемент перестановки.

6. Несложно подсчитать соответствующее число двухстрочных массивов: (Т)(2)-

7. Используя п. (а) теоремы В, выведем требуемые соотношения аналогично тому, как было выведено соотношение (20):

/ А-1 WBWCWB + fcWC-fcV A-k-m-lJ \т) \к) \B-lJ \ I J

(С-I

/ А-1 \ fB\ fC\ fB + k-l\

\A-k-mJ \т) \к J \B-1-1J

1 N (В\ fC\ fB + k-l\ fC-k\

-mJ \mj \kj \ B-l A

A-A-k