AOP_Tom3 (1021738), страница 173
Текст из файла (страница 173)
(а) Поменяйте местами з и 7 в сумме для Аз и сложите атн две суммы. (Ь) Взяв половину данного результата, видим, что (з+ 2) (2п — з — у) ~ (21+ А) (2л — 2з' — /с) ОБ~<з л>э следовательно, 2 Аз„х" = ~ь> )сз" пз"/(1 — 4з) = з/(1 — 4з)з, где а = (1 — т/à — 4з)/2з. Это доказательство сообщил автору Леонард Карлиц (Ьеопагд Саг!Нз) Еще одно доказательство может основываться на взаимосвязи между весами для горизонтальных и вертикальных серий (см. упр.
13). Другой вариант доказательства можно сформулировать при помощи тождества, которое рассмотрено в ответе к упр. 5.2.2- 16 прн /(А) = )з; однако непонятно, как, используя комбинаторику, просто вывести формулу А„= (и/2) 2" 1Б. При н > О й„(з) = у (з) -~- з д (з); и (х) = ~ ХЬь(з)йа ь(з). д-(з) = з"у--М д (х) = ~)' дз( )д -з( )' Полазая С(ю,з) = 2 „д (з)ю", находим, что юзС(ю, х)С(юз, з) = С(ю, з) — 1, Из этого представления можно вывести, что, если 1 = зг1 — 4ю = 1 — 2ю — 2ю — 4ю —, имеем г з С(, 1) = (1-1)/(гю); С,(ю, 1) = 1/(юз) — (1 — 1)/(2юз); С (, 1) = 1/(21з) — 1/(21); С„(ю 1) = 2/(юЗз) 2/(юзз)+(1 1)/нз С)(ю 1) 2/зз 1/зз С (ю Ц 1/зз (1 2ю)/1'+10юз/гз Здесь нижние лзтрихи обозначают дифференцирование по первому параметру, а верхние— по второму параметру.
Аналогично из формулы ю(зС(юз, з) + С(ю, з) ) Н(ю, з) = Н(ю, з) — 1 4Н НИТ2 БН 1.0Х БН БТХ ОБС2 12ИР СИРА Л. 7Н БТА И-Н,1 ТИРОТ,2 ТИРОТ+Н,г 0,4 7Р ТИРОТ,2 БН ТИРОТ+Н,2 Лт-Я-С в в В в  — А В-А абдт-В-С ! Н" (и51) = — ш/1' — ш/1'+ гш/1'+ (2ш'+ 20ш')/1'. Н (од 1) = ш/1, Все эти манипуляции формулами выполнены вручную, но современные программные средства позволяют проделать то же самое значительно быстрее на компьютере. В принципе, таким способом можно получить все моменты этого распределения. Производящая функция д„(т) также представляет 2 о"~""" '"тто'""'ы "г'" по всем деревьям с и + 1 узлами (см.
унр, 2,3.4.5 — 5). Интересно отметить, что С(ш,з) равна Г( — шт, т)/г ( — ш, т), где Е(т,д) = 2 тэ>ох"д" /Пл,(1 — д ); коэффициент при дшо" в е(з,д) равен числу разбиений т ж рл + + р„, таких, что рз > рзэл + 2 при 1 < / < п и р > 0 (см. упр 5 1.1 -16). 16. Ясно, что при Ь = 2 лваксимум достигается на пути, проходящем через правый верхний угол решеточной диаграммы, и равен ((н/2) + 1) При произвольном значении Ь соответствующее число равно /(.,Ь) = (",) (",') + (;) (д+ 1), где д и г определяются теоремой Н; перестановка, в которой аов л = 1+ д(Ь вЂ” в) + (г — 1)(1< с) при 1 < 1 < Ь и о' > О, максимизирует число инверсий в каждой из ( ) пар упорядоченных подпоследовательл настей. Максимальное число перемещений получится, если в формуле (6) подставить / вместо /.
17, Вдииствениая 2-упорядоченная перестановка множества (1, 2,..., 2п) с ("~') инверсиями — это л+1 1 и+2 2 ... 2п п. Применяя данную идею рекурсивно, получим перестановку, в которой добавлена единица к каждому элементу последовательности (2 — 1) и 1 О, где 77 обозначает операцию записи целого в ниде аразрядного двоичного числа с я н последующей записью его двоичных разрядов в обратном порядке (справа налево)! 18. Вынесем за скобки общий множитель и положим )п = 4М(я; требуется минимизировать сумму 2 '„, Ь,7 /Ь, о при условии, что Ьо = 1. В результате дифференциронания получается соотношение Ьо = 4Ьо, Ь, ьм которое имеет решение (2' — 1) 18 Ьв = 2'+' -2(1+ 1) + 18 Уль Минилшльное значение исходной оценки равно (1 — 2 ') хм Юг~~ '~ДЛ'т~ До О/ /2'тн мдо '1, при 1 -о со эта величина быстро сходится к йлиЯМ/2 .
Ниже приведены типичные "оптимальные" значения Ь при Х = 1000 [см. также табл. 6): Ьо 57.64, Ь1 6 13, Ьо = 1; Ьо 135.30, Ьо 22.05, Ьо 4.45, Ьо = 1; Ь~ 284.46, Ьз 67.23, Ьо 16.34, Ьо 4.03, Ло = 1; Ьо 9164.74, Ьв 12294.05, Ьо 7119.55, Ьв 2708.95, Ьв 835.50,. Ьо 232 00, Ьз 61.13, Ьо 15 69., Ь| 3 97, Ьо = 1. 10. Пусть 9(п, .Ь) = ̈́— 1+2 „«од/(дд Ьг), где ди г определены в теореме Н. Подставьте д вместо / в формуле (6). 20. (Сформулировать это на бумаге труднее, чем объяснить на пальцах.) Предположим, что Ь-упорядоченный массив К«..., Яи был Л-рассартирован, и пусть 1 < 1 < Лр — Ро наша цель — показать, что К, < К,~.ь.
Найдем и, и, такие, что 1 = к и 1+ Ь = о (по модулю Л), 1 < и,о < Л. Применим теперь лемму Ь при хз = К„+1 «ю у, = К„еб «ю Затеи первые г элементов К„, К„еь, ..., К„ты «ь из уь будут соответственно < последним г элементам К„+ь, К еьеь,, К,ее+0 «ь иэ хь, где г — наибольшее целое число, такое, что и+ й+ (г — 1)Л < 1ч'. 21. Если хЛ+уй = х Л+ уй, имеем (х-х ) Ь = (у' -у) Л, так что х' = х+ 11 н у' = р — 15 для некоторых целых Ь Пусть Л'Л+ Л'Л = 1; тогда и = (пЛ')Л+ (пЛ') Л, так что любое целое и имеет единственное представление в виде и = хЛ + уЛ, где О < г. < Л, а и — - порождаемое тогда и только тогда, когда у > О.
Пусть аналогично Ьй — Л вЂ” Ь вЂ” и = х~Л+ р~й; тогда (х -ь х') Л -ь (у + у') Л = ЛЬ вЂ” Л вЂ” Л. Следовательно, х + х':— Л вЂ” 1 (по модулю Л) н должно быть х+ х' = Л вЂ” 1. Отсюда у+ у' = -1 и у > 0 тогда и только тогда, когда р' < О Симметричность этого результата свидетельствует о том, что точно 1(Л вЂ” 1)(Л вЂ” 1) положительных целых можно представить в предлагаемом виде. Этот результат впервые получен Сильвестром (Бу!чевсег) (МасЬетаИса) с)иеэбопэ, ячйЬ 11ье1г Яо)~Воок, Ггот гЬе 'Ег1исабола1 Т1теэ' 41 (1884), 21), 22. Чтобы избежать громоздких формул, рассмотрим э = 4 в качестве "полномочного" представителя общего случая Пусть гм — наименьшее число, которое можно представить в виде 15ао+ 31а~ + и конгруэнтное Л (по модулю 15). Тогда нетрудно подсчитать, что Л = 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14, пь = 0 31 62 63 94 125 126 127 158 189 190 221 252 253 254.
Следовательно, 239 = 2 (2 — 1)-1 — наибольшее среди чисел, которые нельзя представать 4 4 в таком виде, а суммарное количество таких чисел есть хэ = (п~ — 1 + пг — 2 + . + пы — 14)/15 = (2+ 4+ 4+ б+ 8+ 8) + 8+ (10+ 12+ 12 ~-14+ 16+ 16) + 16 =2хз-ь8 9. В общем случае х, = 2х, ~ + 2* '(2' '+ 1). Ответы на другие вопросы — соответственно 2м + 2' + 2 и 2' '(2* + е — Ц + 2.
23. Каждое из Х чисел имеет не более Д!меэ — 1)(Л,е~ — 1)/Л,) инверсий в своем подмассиве. 24. (Решение получено совместно с В. Праттом (ч'. Ртам). Построим Л-возвратную перестановку множества (1, 2,..., Лч) следующим образом. Начав с пустых позиций о« .. ап, выполним при / = 2, 3, 4,... шаг /Л Слева направо заполняем пустые позиции о„используя наименьшее число, которое еще не появилось в перестановке, всякий раз, когда (2 — 1) у — 1 ь есть положительное целое число, которое можно представить в виде, описанном в упр. 22. Процесс продолжается до тех пор, пока не буд т заполнены все позиции. Так, 2-возвратной перестановкой при Лг = 20 будет 6 2 1 9 4 3 12 7 5 15 10 8 17 13 11 19 16 14 20 18.
При всех Ь > Л Ь-возвратная перестановка (2 — 1)-упорядочена. Если 2" < 7 < Лг/(2ь — 1), то на у-м шаго заполняется ровно 2 — 1 позиций, причем (Л + 1)-я нз них добавляет, по л крайней мере, 2ь ' — 2Л к чиглу перемещений записей, требуемых для (2 ' -1)-сортировки этой перестановки. Следовательно, число перемещений, необходимых для сортировки Л- возвратной перестановки со смещениями Л, = 2' — 1 при ГГ = 2""'(2" — 1), заведомо больше 2 > е 1ч" 7 .
В. Пратт обобщил эта построение для обширного семейства аналогичных зь-4 последовательностей, включая (12), в своей докторской диссертации (Яьэл(огд Пшгегвсу, 1972). Некоторые эарпстпческие методы, позволяющие найти такие перестановки, которые нуждаются даже в болыпем чнгле перезаписей, найдены Х. Эркио (Н. Егй!о), В1Т 20 (1980), 130-136. Слг. также Ъе!ээ, Бедбев!сй, Х А!ЗоП!Ьтя 11 (1990)., 242-251, где предлагается дальнейшее усовершенствование построения Пратта. 25. Рк~л ,'этот результат получен Г Б Манном (Н.
Б. Мапл), Есопошегг!са 13 (1945), 256), так как перестановка должна начинаться либо с 1, либо с 21. Имеется не более (Х/2) инверсий; общее число инверсий равно Х вЂ” 1 2Х Рл + — Ря о 5 (См. упр. 128. 12) Обратите внимание на то, что Ркэч перестановок можно удобно представить азбукой Морзе (последояательностью точек и тиро), где тире соответствует инверсии (см.
Упр. 4.5.3. 32). Сдедовательно, мы нашли общее число тире во всех последолательностях точек и тире, имеющих длину Х. Приведенные выкдадки показывают, что случайная 3- и 2-упорядоченная перестановка имеет грубо э(ф +2ф ~)Х = б 'Х/з/5 ж .276Х инверсий. Но если случайная перестановка является З-рассортироаанной, а затем 2-рассортированной, то, как показано в упр. 42, она нмгет = !У/4 инверсий; если же сначала она является 2-рассортированной, а затем— З-рассортированной, то она имеет — Х/3 инверсий. 26. Да, пример самого короткого из них — 4 1 3 7 2 6 8 5.
Здесь имеется 9 инверсий. Б общем случае конструкция азьь, = ЗЬ + 4я при — 1 < э < 1 дает 3-, 5- и 7-упорядоченные массивы, которые имеют приблизительно -"Ю ~шверсий. Когда й! шоб 3 = 2, эта конструкция — наилучшая из возможных. 27. (а) См. Х А!8ог!гйшэ 15 (1993), 101-124. Более простое доказательство, которое показыеает, что с может быть любой константой < -', было независпмо получено Ч. Г. Плакстоном (С.
С. Р!ах!оп) и Т. Сьюэлом (Т. Зпе!), Ь А!ЗоНгбтв 23 (1997), 221-240. (Ь) Это очевидно, если ш > -с ()пХ/)и !и%)~. В протилномслучае Х '7 '" > Х(!пХ) . Р. Э. Кифер (Б. Е. СУРЬгг) (Б1СОМР 22 (1993), 62 — 71) нашел более строгое огравичение П(Ж(!обХ)~/ !об!об !г') длЯ слУчан, если смещениЯ УдовлетвоРЯют неРавенствУ Ьцю > Ь, пРн всех э и если последовательность сортировки формируется знк, как описано в упр. 5.3.4 — 2.
На сегодняшний день неизвестно нетривиальное выражение нижнего асимптотического предела для среднего значения времеви выполнения. 28. 209 109 41 19 5 1, как следует из (11). Но возможна и лучшая последовательность смещений (см. Упр. 29). 29. Б результате экспериментов Ш. Триболе (С.
ТНЬо!ет) получил в 1971 году последовательности 373 137 53 19 7 3 1 (В„„ — 7210) и 317 101 31 11 3 1 (В„ „ — 8170). (В первой из них время сортировки равно 127720и по сравнению с ш 128593и, когда те же данные соргиронались с последоаательносгью смещений (11).! Б общем случае Триболе предлагает выбирать Ь„равными простому числу, ближайшему к Х'~'. Эксперименты, проведенные в 1972 году Шелби Седжелом (ЯЬе!Ьу 8!ебе!), показыеают, что наилучшее число смещений в последовательности для Ь! < 10000 при таком методе выбора последовательности равно ! = -, ')и( ~/5 7э) Еще одна хорошая последовательность, найденная Робертом гЕ Томлинсоном (мл.) (НоЪегс К Тоггйпэоп, Зг.), — 199 79 31 11 5 1 (В,, = 7950).
Среднее время в этом варианте — — 127260п — оказалось лу ппим из известных на сегодняшний день результатов. Как следует из длительных экспериментов, проведенных Кэрол М. Мак-Нэйми (Саго!е М. МсХашее), наилучшей псхледовательностью из трех смешений будет 45 7 1 (Вь„, щ 18240). Победительницей в "классе четырех смещений", как показали ее эксперименты, оказалась последовательность 91 23 7 1 (В,, ш 11865), однако в довольно широком диапазоне значений смещений результаты получаются примерно одинаковые.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
