H{w, 1) = w/t\ H"{w, 1) = -w/t - fu/t + 2u;/i + {2u? + гйы)/.

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

Производящая функция также представляет г"""""* ""р""*" по всем

деревьям с п -1- 1 узлами (см. упр. 2.3.4.5-5). Интересно отметить, что G{w,z) равна F{-wz,z)/F{-w,z), где Fiz,q) = Е„>о ""VHLiCl - 9*); коэффициент при gz" в

F{z,q) равен числу разбиений тп = pi +----\-Рп, таких, что pj > pj+i + 2 при 1 < j < п и

р„ > О (см. упр. 5.1.1-16).

16. Ясно, что при h = 2 максимум достигается на пути, проходящем через правый верхний угол рещеточной диаграммы, и равен

При произвольном значении h соответствующее число равно

л-«=(;)(Г)-(;)<-)

где g и г определяются теоремой Н; перестановка, в которой

ai+jh = 1-1- q{h - г) Ч- (г - г) [г < г] при l<i</iHJ>0,

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

17. Единственная 2-упорядоченная перестановка множества {1,2,..., 2п} с (") инверсиями - это п+\ 1 п-1-2 2 ... 2п п. Применяя данную идею рекурсивно, получим перестановку, в которой добавлена единица к каждому элементу последовательности (2 - 1) ... 10, где R обозначает операцию записи целого в виде -разрядного двоичного числа с последующей записью его двоичных разрядов в обратном порядке (справа налево)!

18. Вынесем за скобки общий множитель и положим ht = 47V/7r; требуется минимизировать сумму Е!=1 h/hs-i при условии, что /ю = 1. В результате дифференцирования получается соотнощение = 4/iJ i/is+i, которое имеет рещение (2* - 1) Ig/ii = 2"*" - 2(<-1-1)-1-Ight- Минимальное значение исходнойоценки равно (1-2"*)7г -1)дг1+2 /(2 -i) 2i+(*-i)/(2 -1) jjpjj < оо эта величина быстро сходится к N\/ttN/2 .

Ниже приведены типичные "оптимальные" значения h при Л = 1000 (см. также табл. 6):

/12 и 57.64, /11 «6.13, /10 = 1;

/13 и 135.30, /12 и 22.05, hi к 4.45, ho = 1;

/14 и 284.46, /13 и 67.23, /12 и 16.34, hi « 4.03, ho = 1;

/19 и 9164.74, hs « 12294.05, /17 7119.55, /le w 2708.95, /15 и 835.50,

/14 и 232.00, hs « 61.13, /12 « 15.69, hi « 3.97, ho = 1.

19. Пусть g{n, h) = Яг - Ц-Ег<><л 9/(9J+")i ""Де g и г определены в теореме Н. Подставьте д вместо / в формуле (6).

20. (Сформулировать это на бумаге труднее, чем объяснить на пальцах.) Предположим, что fe-упорядоченный массив Ri,..., Rn был /i-рассортирован, и пусть 1 < i < N - к; наша цель - показать, что К{ < Ki+k. Найдем и, v, такие, что i = uHi + k = v (по модулю h), 1 < u,v < h. Применим теперь лемму L при Xj = Kv+(j-i)h, Vj = Ku+{j-i)h- Затем первые г элементов Ки, Ки+н, Ku+(r-i)h из ук будут соответственно < последним г элементам Ки+к, K+k+h, u+fc+(r-i)/i из Хк, где г - наибольшее целое число, такое, что и + к + {г - l)h < N.

21. Если xh + yk = xh + yk, имеем {x - x)h = [у -у)к, так что х = x + tk иу - y - th для некоторых целых t. Пусть hh + кк - 1; тогда п = {nh)h + {пк)к, так что любое целое п имеет единственное представление в виде п = xh + ук, где О < х < к, а, п - порождаемое тогда и только тогда, когда у > 0. Пусть аналогично hk-h - к - п = xh + ук; тогда {х + x)h + (у + у)к = hk - h - к. Следовательно, х + х = к - 1 (по модулю к) и должно быть X + х = к - 1. Отсюда у--у = -1 иу>0 тогда и только тогда, когда у < 0.

Симметричность этого результата свидетельствует о том, что точно (/i - 1){к - 1) положительных целых можно представить в предлагаемом виде. Этот результат впервые получен Сильвестром (Sylvester) [MatiiematicaJ Questions, with their Solutions, from the Educational Times 41 (1884), 21].

22. Чтобы избежать громоздких формул, рассмотрим s = 4 в качестве "полномочного" представителя общего случая. Пусть Пк - наименьшее число, которое можно представить в виде 15ао + 3101 Н----и конгруэнтное к (по модулю 15). Тогда нетрудно подсчитать, что

fe = О 1 2 З 4 5 6 7 8 9 10 11 12 13 14, nfc = О 31 62 63 94 125 126 127 158 189 190 221 252 253 254.

Следовательно, 239 = 2(2 -1) -1 - наибольшее среди чисел, которые нельзя представить в таком виде, а суммарное количество таких чисел есть

14 = (П1 - 1+ П2 - 2 + • + П14 - 14)/15

= (2 + 4 + 4 + 6 + 8 + 8) + 8 + (10 + 12 + 12 + 14 + 16 + 16) + 16 = 2а;з + 8 9.

В общем случае Xs = 2xs-\ + 2~(2" + 1).

Ответы на другие вопросы - соответственно 2 + 2* + 2 и 2"(2 + s - 1) + 2.

23. Каждое из N чисел имеет не более [(/is+2 - l)(/is+i ~ 1) *«1 инверсий в своем подмассиве.

24. (Решение получено совместно с В. Праттом (V. Pratt). Построим /i-возвратную перестановку множества {1,2,..., N} следующим образом. Начав с пустых позиций oi... on , выполним при j = 2,3,4,... шаг j. Слева направо заполняем пустые позиции щ, используя наименьшее число, которое еще не появилось в перестановке, всякий раз, когда (2 - 1) j - г есть положительное целое число, которое можно представить в виде, описанном в упр. 22. Процесс продолжается до тех пор, пока не будут заполнены все позиции. Так, 2-возвратной перестановкой при N = 20 будет

6 2 1 9 4 З 12 7 5 15 10 8 17 13 11 19 16 14 20 18.

При всех k>h /i-возвратная перестановка (2* - 1)-упорядочена. Если < j < N/{2 - 1), то на j-M шаге заполняется ровно 2 - 1 позиций, причем (fe + 1)-я из них добавляет, по крайней мере, 2" -2fe к числу перемещений записей, требуемых для (2" - 1)-сортировки этой перестановки. Следовательно, число перемещений, необходимых для сортировки h-возвратной перестановки со смещениями hs = 2 - 1 при N = 2"" {2 - 1), заведомо больше 2З/1-4 у Q Пратт обобщил это построение для обширного семейства аналогичных

последовательностей, включая (12), в своей докторской диссертации (Stanford University, 1972). Некоторые эвристические методы, позволяющие найти такие перестановки, которые нуждаются даже в большем числе перезаписей, найдены X. Эркио (Н. Erlcio), BIT 20 (1980), 130-136. См. также Weiss, Sedgewick, J. Algorithms 11 (1990), 242-251, где предлагается дальнейшее усовершенствование построения Пратта.

25. Fn+1 [этот результат получен Г. Б. Манном (И. В. Mann), Econometrica 13 (1945), 256], так как перестановка должна начинаться либо с 1, либо с 2 1. Имеется не более [N/2} инверсий; общее число инверсий равно

7V - 1 27V „

-T-Fn + -Fn-i. 5 5

(См. упр. 1.2.8-12.) Обратите внимание на то, что Fjv+i перестановок можно удобно представить азбукой Морзе (последовательностью точек и тире), где тире соответствует инверсии (см. упр. 4.5.3-32). Следовательно, мы нашли общее число тире во всех последовательностях точек и тире, имеющих длину 7V.

Приведенные выкладки показывают, что случайная 3- и 2-упорядоченная перестановка имеет грубо {ф- + 2ф-)М = ф-М/у/Ех .2767V инверсий. Но если случайная перестановка является 3-рассортированной, а затем 2-рассортированной, то, как показано в упр. 42, она имеет и 7V/4 инверсий; если же сначала она является 2-рассортированной, а затем - 3-рассортированной, то она имеет 7V/3 инверсий.

26. Да; пример самого короткого из них - 4137268 5. Здесь имеется 9 инверсий. В общем случае конструкция азк+s = Зк + is при - 1 < s < 1 дает 3-, 5- и 7-упорядоченные массивы, которые имеют приблизительно 7V инверсий. Когда 7V mod 3 = 2, эта конструкция - наилучшая из возможных.

27. (а) См. J. Algorithms 15 (1993), 101-124. Более простое доказательство, которое показывает, что с может быть любой константой < , было независимо получено Ч. Г. Плаксто-ном (С. G. Plaxton) и Т. Сьюэлом (Т. Suel), J. Algorithms 23 (1997), 221-240. (b) Это очевидно, еслит > c(ln7V/lnln7V)2. В противном случае TV+Z > N(lniV) P. Э. Кифер (R. Е. Cyplier) [SICOMP 22 (1993), 62-71] нашел более строгое ограничение f2(N(iog7V)7 log log TV) для случая, если смещения удовлетворяют неравенству h+i > hs при всех s и если последовательность сортировки формируется так, как описано в упр. 5.3.4-2. На сегодняшний день неизвестно нетривиальное выражение нижнего асимптотического предела для среднего значения времени выполнения.

28. 209 109 41 19 5 1, как следует из (11). Но возможна и лучшая последовательность смещений (см. упр. 29).

29. В результате экспериментов Ш. Триболе (С. Tribolet) получил в 1971 году последовательности 373 137 53 19 7 3 1 (Bave « 7210) и 317 101 31 И 3 1 (Bave 8170). [В первой из них время сортировки равно х 127720и по сравнению с » 128593и, когда те же данные сортировались с последовательностью смещений (11)] В общем случае Триболе предлагает выбирать hs равными простому числу, ближайшему к TV*. Эксперименты, проведенные в 1972 году Шелби Седжелом (Shelby Siegel), показывают, что наилучшее число смещений в последовательности для 7V < 10000 при таком методе выбора последовательности равно t« ln(7V/5.75).

Еще одна хорошая последовательность, найденная Робертом Л. Томлинсоном (мл.) (Robert L. Tomlinson, Jr.), - 199 79 31 И 5 1 (Bave » 7950). Среднее время в этом варианте - и 127260и - оказалось лучшим из известных на сегодняшний день результатов.

Как следует из длительных экспериментов, проведенных Кэрол М. Мак-Нэйми (Carole М. McNamee), наилучшей последовательностью из трех смешений будет 45 7 1 (Bave и 18240). Победительницей в "классе четырех смещений" как показали ее эксперименты.