проходить выше либо на уровне того же зигзага, что и в предыдущий раз. Таким образом, массив q заполняется слева направо и снизу вверх; для того чтобы заставить процесс идти в обратном направлении, мы должны организовать движение слева направо и сверху вниз.

HI. [Инициализация.] Присвоить Ру О, 1 < j < и 1 < г < п[. Затем присвоить i <- 1 и j <г~ щ.

Н2. [Поиск ненулевой ячейки.] Если Qij > О, перейти к шагу НЗ. В противном случае, если г < nj, увеличить г на 1 и повторить этот шаг. В противном случае, если j > 1, уменьшить j на 1, присвоить г <- 1 и повторить этот шаг. В противном случае остановить процесс (массив q теперь обнулен).

НЗ. [Уменьшение q, подготовка к движению по зигзагу.] Уменьшить qtj на 1 и присвоить I <- i, к <- ni.

Н4. [Переход вниз или влево.] Если / < п, ир;*, > pi+ik, увеличить Z на 1 и вернуться к шагу Н4. В противном случае, если к > j, уменьшить А; на 1 и вернуться к шагу Н4, В противном случае вернуться к шагу Н2,

Первый зигзаг для данного столбца j заканчивается приращением pij, поскольку pij < • • • < Pn.j влечет за собой p„j > 0. Каждый последующий путь для столбца j проходит ниже или па том же уровне, что и предыдущий, так что он также закончится на p„j. Неравенства, которые используются в этом способе, свидетельствуют о том, что построенный алгоритм является обратным по отношению к описанному при постановке задачи. [J. Combinatorial Theory А21 (1976), 216-221.]

36. (а) Коэффициент при г"* есть число решений т - Yhijqij, так что можно распространить на данный случай результат предыдущего упражнения. (Ь) Если ai, ..., а*, - любые положительные целые числа, можно доказать, используя индукцию по к, что

1/(1 - .)(1 -.-)... (1 -.<") = ()/ai .. .а, + 0(т*-).

Число разбиений т на не более чем п частей равно, таким образом, („1 J/n\ + 0{m~) при фиксированном п, как следует из упр. 5.1.1-15. Это также асимптотическое число разбиений т= pi-\-----hPn, когда части различны - pi > > рп > О (см. упр. 5.1,1-16). Таким

образом, число обратных плоских разбиений асимптотически приближается к N{)/п1 + 0(т"~), если имеется N диаграмм данной формы из п ячеек. Из п. (а) это также есть („i)/n/iij +0{т"-). [Studies in Applied Math. 50 (1971), 167-188, 259-279.]

37. Плоское разбиение на прямоугольнике эквивалентно обратному плоскому разбиению, так что длины уголков дают нам производящую функцию 1/П{=1Щ=1(1 ~ г""-") на прямоугольнике г х с. Если положим г, с - оо, то получим ответ в очень элегантном виде: 1/(1 - г)(1 - г)(1 - z) .... [Вывод принадлежит Мак-Магону и опубликован в Philosophical Transactions 211 (1912), 75-110, 345-373, но там он имел гораздо более сложную форму. Первым простое доказательство нашел Леонард Карлиц (Leonard Carlitz), Acta Arithmetica 13 (1967), 29-47.]

38. (a) Вероятность равна 1/n при к = I = 1; в противном случае, применяя индукцию по к + 1, получим

пР{1 \ {го}, J) + пР{1, J \ {jo}) (djQb 4-dajo)/(nd,ob...d. ,6dajo .daj,-i)

ndiojo digb+dajo

(b) Суммирование no всем /и J дает n"(l--dn,)... (l-l-d i)J {l+d~l)... (l+di), что, как легко видеть, равно f{T\ {{a,b)})/f(T).

(c) Суммирование по всем угловым ячейкам дает 1, поскольку каждый путь заканчивается в какой-либо угловой ячейке. Таким образом, /(Г \ {{а,Ь)}) = f{T), а это

доказывает теорему Н, если применить индукцию по п. Более того, если разместить п в угловой ячейке в конце случайного пути и повторить процесс на оставшихся п - 1 ячейках, получится каждый вариант диаграммы с вероятностью 1 (Г). [Advances in Math. 31 (1979), 104-109.]

39. (а) Qii... Qi„ будут иметь вид bi.. .b„, т. е. будут представлять собой таблицу инверсий исходных перестановок Рц ... Pi„ (см. раздел 5.1.1).

(b) <3ii • • • Qui - таблица инверсий с обратным знаком (-Ci)... {-С„) из упр. 5.1.1-7.

(c) Это условие, очевидно, предусматривается на шаге РЗ.

(d) (23) ((24). (о о)); (") -> ((34). (о "о))- Этот пример показывает, что нельзя выполнять шаг РЗ в обратном направлении, не просмотрев массив Р.

(f) Следующий алгоритм корректен, но не очевиден.

Q1. [Цикл по Выполнить шаги Q2 и Q3 для каждой ячейки {i,j) массива в

лексикографическом порядке (т. е. сверху вниз и слева направо в каждой строке), затем прекратить выполнение процедуры.

Q2. [Изменение Q.] Найти "первого кандидата" (г, s) по правилу, которое будет изложено ниже. Затем присвоить Qi(k+i) Qik - 1 для j <к < s. Q3. [Восстановление Р в Присвоить К (- Р. Затем выполнять следующие

операции до тех пор, пока не будет выполнено условие (г, s) = (г,). ЕслиР(г-1)8 > Pr(s-i), присвоить Prs «- P(r-i)s И Г «- Г - 1; в противном случае присвоить Prs «- Pr{s-i) и s «- s - 1. и, наконец, присвоить Pij -i- К. На шаге Q2 ячейка (г,s) является кандидатом, если s > и Qis < О, и г = г - Qis. Пусть Т - ориентированное дерево, построенное в соответствии с указанием. Один из основных инвариантов алгоритма Q состоит в том, что на этом дереве будет существовать путь от (г, s) к (г, j) в Г всякий раз, когда (г, s) является кандидатом на шаге Q2. Обратный путь к нему можно закодировать последовательностью букв D, Q и R, означающих, что мы начали в ячейке затем спустились (D) или пошли вправо (R), или закончили (Q). Первый кандидат - зто один из кандидатов, код которого в лексикографическом смысле стоит раньше других; интуитивно кажется, что он должен быть крайним слева и снизу по отношению к "конкурентам".

Например, кандидатами при = (1,1) в примере п. (е) являются (3,1), (4, 2), (2, 3), (2,4) и (1,6). Им соответствуют коды DD.Q, DDDRQ, RDRQ, RDRRQ и RRRRRQ; из них первым будет (4, 2).

Алгоритм Р представляет собой несколько упрощенную версию построения, описанного без доказательства в работе, опубликованной в журнале Функциональный анализ и его приложения, 26,3 (1992), 80-82. Доказательство корректности этого построения отнюдь не очевидно и дано Ж.-К. Новелли (J.-C. Novelli), И. Паком (I. Рак) и А. В. Стояновским (А. V. Stoyanovskii) в Disc. Math, and Theoretical Сотр. Sci. 1 (1997), 53-67.

40. Эквивалентный процесс проанализирован в работе Н. Rost, Zeitschrift fUr Walirscliein-lichkeitstheorie und verwandte Gebiete 58 (1981), 41-53.

41. (Решение предложено P. У. Флойдом (R. W. Floyd).) Операция удаления-вставки фактически перемещает только а;. В процессе ее выполнения незатронутые элементы сохраняют порядок. Таким образом, если перестановку тг можно рассортировать при помощи к

операций удаления-вставки, то она имеет возрастающую подпоследовательность длиной п - fe, и наоборот. Следовательно, dis(7r) = п - (длина самой длинной возрастающей подпоследовательности в тг) = п -Ь (длина строки 1 в теореме А).

М. Л. Фредман (М. L. FVedman) доказал, что наименьшее количество сравнений, необходимое для вычисления этой длины, равно nlgn -nig Ig n-t-0(п) [Discrete JVfatii. 11 (1975), 29-35].

42. Постройте мультиграф с вершинами {Ол, 1l, 1л,. • •, пь, пя, (n-t-1),} и ребрами кп - (к+ 1)l при О < fe < п, включите также ребра Ол - 7л, 7ь - 1l, 1л - 2ь, 2r - 4l, 4л - 5l, 5л - 3l, Зл - 6л, 6l - 8l, которые соответствуют "узам" в Lobelia fervens. К каждой вершине подходит в точности два ребра, так что связанные компоненты являются циклами: (Ол 1l 7l 6л Зл 4 2л 3l 5л 6 8ь 7л)(1л 2L)(4л 5l). Некоторая операция перебрасывания изменяет количество циклов на -1, О или -t-1. Таким образом, нам понадобится, по крайней мере, пять операций для того, чтобы прийти к восьми циклам (Ол lL)(lл 2l) ... (7л 8l). [j. Kececioglu, D. Sankoff, Lecture Notes in Сотр. Sci. 807 (1994), 307-325.]

Первая операция должна разорвать узы 6l - 8l, поскольку мы не достигнем никакого нового цикла после разрыва двух уз, которые имеют одинаковую ориентацию слева направо в линейном представлении. В результате после одной операции появляется пять вариантов, а именно - д?двдз9ь94 92 91, 57*313254355356, 9?91929бдздьд4, 57*515254555653* и двдз9&94 92 9дт, еще четырех операций достаточно для того, чтобы рассортировать все, кроме второй из них.

Существует 2 7! = 645 120 разных вариантов компоновки gi ... gj и 179 904 из них находятся на расстоянии < 5 от порядка в молекуле ДНК табака.

[Эффективный алгоритм поиска наилучшего способа сортировки любой перестановки со знаком посредством реверсирования был изложен в работе S. Hannenhalli, Р. Pevzner, JACM 46 (1999), 1-27, а усовершенствован - в работе Kaplan, Shamir, Tarjan, SODA 8 (1997), 344-351.]

43. Обозначим компоновку наподобие 57*515254555з5б* посредством перестановки со знаком 7124536. Если существует отрицательный элемент, например fe, но отсутствует fe - 1, одна операция перебрасывания создаст двойной цикл ((fe-l)лfeL)• Аналогично, если имеется fe, но отсутствует fe-t- 1, единственная операция перебрасывания сформирует (feH (fe-t-l)i,). И если все операции такого вида удаляют все отрицательные элементы, то единственное перебрасывание формирует два двойных цикла. Если отсутствуют отрицательные элементы, а перестановка не рассортирована, некоторые из перебрасываний будут сохранять количество циклов. Следовательно, за < п перебрасываний можно выполнить сортировку, если данная перестановка имеет отрицательный элемент; в противном случае необходимое количество перебрасываний составит < п -t-1.

Если п четное, перестановка п (п-1) ... 1 требует п -t-1 перебрасываний, поскольку в ней будет один цикл после первого перебрасывания. Если п > З нечетно, то, рассуждая аналогично, приходим к выводу, что для перестановки 2 1 Зп (п-1) ... 4 потребуется n-t-1 операция.

44. Пусть Cfc - число циклов длиной 2fe в мультиграфе из ответа к предыдущему упражнению. Верхняя граница для среднего значения cjt может быть найдена следующим образом. Общее число потенциальных 2fe-циклoв равно 2*(n-t- l)-/(2fe), поскольку мы можем выбрать (n-t-1)-способами последовательность к различных ребер из {Ол - 1l, ... ,пл - (п -t- и ориентировать их 2* способами. Таким образом, каждый цикл будет подсчитан 2fe раз, включая и невозможные случаи наподобие (1л 2ь 2л 3l), (1л 2l 3l 2л Зл 4i,) и (1л 2l 6л Tl 4l Зл 2л 3l 6l 5л). Если к <п, каждый возможный 2fe-цикл появляется точно в 2""*(п - fe)! перестановках со знаком. Например, рассмотрим случай, когда fe = 5,