Д. Кнут - Искусство программирования том 4 выпуск 4 - 2007 (1119377), страница 26
Текст из файла (страница 26)
— Прнмеч. нор. сделано для вълкпИапаса.ого 108 ОТВЕТЫ К УПРАЖНЕНИЯМ имеется 38 таких путей, а именно (8,6,6,8,4,6) путей от 0123 до соответственно (1001,0010,0012,0100,0111,0120).) (с() Истинно, поскольку отношение покрытая из ответа (с) обладает лево-правой симметрией. (г' С г' тогда и только тогда, когда шу < в' для О < у < 2п, где иу определено в упражнении 10.
Если юо... злзо представляет собой обход червем леса Р, то обратная последовательность таз„... зло представляет собой обход леса си. Обратите внимание, что отношение покрытия изменяет только одну координату злу. Вычислить Гй гч и г О гч можно, если искать минимумы и максимумы для ю, а не для с.) (е) См, упражнение 9.
(Таким образом, Р3.Р' С Р г1 гт н т.д., как в упражнении 27 (1).) Пртлмечанпе: Стенлн разработал свою решетку в ЯЬопасс( Япагсег1у, 13 (1975), 222-223. Поскольку три важные решетки определены на одних и тех же элементах, требуются три обозначения для различных упорядочений; здесь для этого использованы символы <, -< н ч., напоминающие первью буквы фамилий Креверас, Тамари и Стеклил. 29.
Если мы "склеим" шесть правильных пятиугольников, то получим 14 вершин, координаты которых после соответствующих поворотов н масштабирования будут следующими: ршзо = рспп = рзоса — — рз1оа = (-1, з/3, 2/ф); рвиа = рззоо = (ф, з/Зф,О); рзпо = розов = (0,0,2); рзюо = Робело = (2,0,2/ф); роша = рлюо = ( Л АЗ 0); рзаоо = ряюо = ( — ф, з/3/ф, 0), где (я, у, л) означает (я, -у, л), а (х, у, л) означает (я,у, -л).
Но тогда три четырехугольные "грани" не являются квадратами; более того, нх вершины даже не лежат в одной плоскости. (Однако можно получить похожее тело с правильными квадратами и неправильными пятиугольниками, соединяя два подходящих тетраэдра и обрезая три осклеенныхо угла. Альтернативные множества координат для ассоциаздра, представляющие определенный математический интерес, но не имеющие никакой внешней привлекательности для глаз, рассматриваются Гюнтером Цнглером (Ойп1ег Е(ей)ег) в Ъесгпгеэ оп Ро1узореэ (Хазу Уог)с: Брппйег, 1995), пример 9.11.) 30. (а) /о 1... /зО, поскольку внутренний узел у в симметричном порядке обхода имеет непустое правое поддерево тогда и только тогда, когда внутренний узел у + 1 в симметричном порядке обхода имеет пустое левое полдерева.
(Ь) В общем случае, если след имеет вид 1жОо'+з1"*+зОо'+ ... 1гл+'Оо"+з, нам нужно подсчитать все бинарные деревья, узлы которых в симметричном порядке обхода имеют спецификацию ВР'Хйт' ВВУз Мул*В... Вв'ЖУо", где В означает "аба полдерева не пусты",  — "правое поддерево не пустое, левое — пусто~", Ь вЂ” "левое поддерево не пустое, правое — пустое", а М вЂ” "аба поддерева пусты". Это количество ла оригинале указано, что ннсотсн в внлу нвпислиие флинлин Столин по-русски.
— Примеч. пор. сделано для ькьуьк! н(апаса.ого ОТВЕТЫ К УПРАЖНЕНИЯМ 109 в общем случае равно РАЙ+91 Рз+4З Рь+Чь и в коикретиом указанном в условии упражиеиия случае составляет 1+О О+О 1+О 5+3 О+О О+О О+2 О+О 1+2 = 240 240. (с) й = О тогда и только тогда, когда су+1 > с;, в соответствии с упражнением 3. (с1) В общем случае след Г 1Г' равен 71... У„А Д... Д, в соответствии с упражиеиием 27 (а); след ГТГ' рввеи 71... Х„Ч Д... Д, согласно ответу (а) и упражиеиию 27 (Й).
(Тот факт, что в решетке Тамари всегда имеется комплемеитариый элемент, доказан Г. Лаксером (Н. 1 аЪег); см. С. Сгасвег, Сепега) ХаЫсе ТИеогу (1878), упражиеиие 1.6.30.) 31. (а) 2" ' (см. упражнение 6.2.2-5). (Ь) с1 « с„;да...,6„< 1;изе > Овытекаете +..+е„= и — у; Й;+1 < Йу + 1; Р1 « ° Р» » ° ° Р„для некоторого у; из з > 0 вытекает в; = = п — з; и1 » и„; ху+1 < з + 2. (Прочие ограничения, применимые в общем случае, снижают количество возможных кортежей с данными свойствами до 2" 1 в каждом конкретном случае.) (с) Истинно только в и случаях из 2" '.
(Но Гт лаалетсл вырожлеияым.) (6) Вырожденный лес со следом ~~...,7„обладает тем свойством, что су+~ = = с. + Д. Элементы у < к являются братьями тогда и только тогда, когда Д = = Д+1 = ° = уь 1 = О. Таким образом, если Г" является вырождеииым лесом со следом 71... 7'„А Д... У„', то Г" к Г и Г" к Г'; следовательно, Г" к ГдГ' -1 ГЛ.Г'. Согласно ответу (Ь), мы также имеем Г1Г' -1 Г".
Аяалогичио доказывается и то, что ГУ Г' = ГТГ' является вырождеииым лесом со следом 71... ~„Ч Д... Д. Таким образом, когда решетки Кревераса и Тамари ограиичеиы вырожденными лесами„они становятся идентичными булевой решетке подмножеств (1,..., и — Ц. (Этот результат в случае решетки Тамари открыт Д. Марковски (С.
Маг)юмв1су), Оп1ег„й (1992), 265-290, статья которого содержит также описание многих других свойств решеток Тамары.) 32. Пусть Г и Г' имеют з-коордииаты соответственно в1... в„и в',... в'„, Назовем индекс 1 заморожеияььм (угохеп), если в < в' или у = О. Мы хотим определить значения замороженных координат и максимизировать остальные, Пусть ве = и и пусть для 0 < и < и вь~ — — з — я + у, где у = шах (1 ~0 < 1 < я, 1 заморожеио, а 1+ з > я) .
Поскольку еь < ву — (й — Я при 0 < я — у < вз, мы имеем в~~ > зь, причем равенство достигается, когда Й вЂ” замороженный индекс. Значения в~~в1'... в'„' соответствуют корректному лесу в соответствии с условием из упражиеиия 27 (а). Если и > Оп 0 ~1 < в~~! = в; — к+ ) и в~~ ~ — — в' — Й вЂ” 1+ у', то сделано для ькькьклн$анаса.ого 110 ОТВЕТЫ К УПРАЖНЕНИЯМ мы имеем в'„'+~ +1 < в~в' для 0 < )' — 1 < в, потому что и этом случае в' +,у' —,у < в;. Поскольку у+ в > й+1 > 1', не может быть 1 > у' или,у' > 1+ ву. Пусть Гв' — лес с координатами, удовлетворяющими условию вь < вгв < в,",.
Тогда ппп (в',„в~') = вы поскольку вь = вь' при замороженном й, и вь = в'„в противном случае. И наоборот, если г "' — лес, такой, что г".1 Г" = Р, должно выполняться вь < < в~' < в~~в. Условие в~в < вь влечет за собой в'„" < в'. А если й — минимальное значение, для которого вьо > в~в', то мы имеем в'„' = в — й + з для некоторого замороженного у, где О < .у < й и 1 + вв > й. Тогда из в'" > ву вытекает й — 1 < в'.", следовательно, в~в + й — 1 < в'~'.
Если у < й, мы имеем в',р < в" = вв, т.е. получаем противоречие. Но из 1 = й вытекаег, что ппп (в~~", в~в) > вь. Чтобы получить первый полудистрибутивный закон, применим этот принцип, заменив Р на Г.[С, а Г' — на Г. Тогда из гипотез Г Ч С -1 Го и Г Ч Н Ч г'" следует, что Г -1 СТН Ч г". Второй полуднстрибутивный закон получается путем применения дуальности к первому. (Ральф Фрис (На[рй асееве) предложил называть й в исевдоооиолиением (рвепбосошр1ешепг) Г' над Р.) 33. (а) Пусть йЛ равно 111МК [й), если 1.11МК[й) ф О; в противном случае пусть оно принимает значение М 1МК[й — П, если й;~ 1, а если это не так, то пусть йЛ равно корю бинарного дерева. Это правило определяет перестановку, поскольку йЛ = у тогда и только тогда, когда либо й = рахепС (() + [7' является правым дочерним узлом), либо й = 1 и 1 является корнем.
Кроме того, йЛ > й, когда 1,11МК[й) = О, и йоЛ < й, когда 31.1МК [й) = О. [Обобщение на г-арные деревья можно найти в работе Р.Н. Ие1- шап, 01встеге МаСЬ., 40 (1982), 171-179.] (Ь) Используя представление (2) из ответа к упражнению 26 ([), мы видим, что в этом случае Л (Г) равно (3 1) (2) (12 6 4) (5) (11 7) (14 13) (9 8) (15) (10).
В общем случае циклы представляют собой семейства лесов, расположенные в уменьшающемся порядке и пределах каждого цикла; узлы пронумерованы в прямом порядке обхода. [См. [1шзйонйв апд Кайв, [11всгесе Май., 62 (1986), 215-218.] (с) Л(го) = роЛр, где р — 'зеркальная" перестановка (1 и) (2 и — 1)..., поскольку в дуальном лесу выполняется обмен Ы.1МК ~-~ 31.1МК и отражение нумерации в прямом порядке обхода. (с)) Разбиение цикла (зухь)(я1...х,„) = (х1...взяв+1 ° ° х )(яв+~ ° хь) соответствует ответу 26 (с). (е) Согласно ответу (и), каждый покрывающий путь соответствует разложению (и...2 1).
Пусть д„— количество таких разложений. Тогда мы получаем рекуррентное соотношение 91 = 1 н 9„= ~ ~",' (и — 1) (", 1)йп7„п поскольку имеется и — 1 выборов, где й †.у = 1, при которых первая перестановка разбивает цикл на части размерами 1 и и — 1„после чего имеется (", з) способов чередования последующих Разложений. Решением РекУРРентного соотношениЯ Явлаетса йв = и" з, посколькУ = 1пп =(и — 1)р" 1. в О х сделано для вълклн[апа[а.ого Отнеты к упрлжнениям ш (См. Л.
Эепев, Майуаг ТЫотялуоз АйиМпш Ма(ета(1)ш) Кп(а(б 1п(еяесепей Коя1ешепуе(, 4 (1959), 63-70. Естественным представляется поиск соответствия между факторизацией и помеченными свободными деревьями, так как количество и тех и других равно н" з. Вероятно, простейшее из них для данного (1 2... и) = (х) ))))... ... (х„) 9„)), где ху < ру, следующее. Предположим, что цикл, содержащий ху н Р) В (ху Ду)... (Хн ) Дв )), пРедставлнет собой (х)... хт), где х1 « ' ' ' хув Если 91 = х, пУсть а = х1., в пРотивном слУчае пУсть а = ппп(га(з; > х)). Можно показвль, что а1...
а„~ — последовательность парковки и — 1 машин из упражне. ния 6А-29, а в упражнении 6.4-31 показана ее связь со свободными деревьями.) 34, Каждый покрывающий путь снизу вверх эквивалентен диаграмме Юнга формы (и — 1„п — 2,..., 1), так что мы можем воспользоваться теоремой 5.1.4Н (см. упражнение 5.3.4-38). (Подсчет таких путей в решетке Тамары остается загадкой: соответствующая последовательность имеет вид 1, 1, 2, 9, 98, 2981, 340 549, ...) 35. Умножьте на и + 1 н обратятесь к АММ, 97 (1990), 626-630. 36.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
