Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 18
Текст из файла (страница 18)
Перемножение этих вероятностей по всем 1 и у приводит к формулировке теоремы Н. Однако такое рассуждение ошибочно, поскольку эти события отнюдь не являются независимыми! Все известные доказательства теоремы Н, основанные на комбинаторных свойствах уголков, были некорректны вплоть до 1992 года (см. упр. 39), хотя и предлагалось несколько непрямых доказательств (см. упр. 35, 36 н 38). Существует интересная связь между теоремой Н и перечислением деревьев, которое рассматривалось в главе 2.Мы вплели, что бинарным деревьям с и узлами соответствуют перестановки, которые можно получить с помощью стека, и что этим перестановкам соответствуют последовательности агав... аэ„п литер 8 и и литер. Х, такие, что кзличество литер $ никогда не бывает менъше колкчества литер Х, если читать последовательность слева направо (см.
упр. 2.2.1-3 и 2.3.1-6). Подобным последовательностям естественным образом сопоставляются диаграммы формы (п,п); в 1-ю строку помещются индексы (, такие, что и; = В, а во 2-ю строку — индексы, при которых а~ = Х. Например, последовательности БББХХЯБХХЯХХ соответствует диаграмма 1 2 3 6 710 4 5 6 91112 Условие, налагаемое на столбцы„удовлетворяется в такой диаграмме в том и только том случае, когда при чтении слева направо число литер Х никогда не превышает числа литер 8.
По теореме Н количество всевозможных диаграмм формы (н,в) равно (2н)! (н+ 1)(н! следовательно, таково же число бинарных деревьев, что согласуется с формулой 2.3.4.4-(14). Более того, если воспользоваться диаграммой формы (н, т) при и > т, то при помощи этого рассуждения можно решить и более общую "задачу о баллотировке", рассмотренную в ответе к упр. 2.2.1-4. Таким образом, теорема Н в качестве простых частных случаев включает в себя некоторые весьма сложные задачи о перечислении. Всякой диаграмме А формы (и, и) из элементов (1, 2,, 2п) соответствуют две диаграммы (Р, ~>) одинаковой формы.
Следувнций способ построения такого соответствия предложен Мак-Магоном [СошЬ(пасогу Апа7уаэ 1 (1915), 130-131). Пусть Р состоит из элементов (1,..., и), расположенных так, как в А, а ~ получается, если взять остальные элементы А, повернуть всю конфигурацию на 180' и заменить и+ 1, и+ 2,..., 2н значениями п„н — 1 соответственно. Например, диаграмма (37) распадается на 1 2 3 6 и 7 10 4 5 8 9 11 12 после поворота и перенумерации имеем 1 2 3 6 1 2 4 5 4 5 ' 3 б Наоборот, каждой паре диаграмм одинаковой формы, состоящих из и элементов н нз не более чем двух строк, соответствует диаграмма формы (и, и). Следовательно (из упр. 7), число перестановок а~ ат...
а„множества (1, 2,..., н), не содержашнх убывающих подлоследовательностей а; > а, > иь прн 1 < у < 15 равно числу бинарных деревьев с и узлами. Интересное взаимно однозначное соответствие между такими перестановками и бинарными деревьями, установленное более прямым способом, чем тот окольный путь через алгоритм 1, которым воспользовались мы, нашел Д. Ротам (см. О. Нскеш, 1пб Ргос. Ееыегя 4 (1975), 58-6Ц; аналогично существует довольно примое соответствие между бинарными деревьями и перестановками„не содержащими подпоследовательностей а > аь > а„.
при 1 < у < Й (см. упр, 2.2.1-5). Числю способов заполнения диаграммы формы (6,4,4,1), очевидно, равно числу способов разметки вершин ориентированного графа (39) (40) которую вывел Роте в 1800 годудля получения таблицы значений 1„прн малых и. Значения для и > 0 равны 1, 1, 2, 4, 10, 26, 76, 232, 764„2 620, 9 496, .... Рассмотрим другой способ. Пусть имеется и циклов из двух элементов и (и — 2А) единичных циклов.
Существует (",) способов выбора неподвижных точек, и полиномиальный коэффициент (2Й)(~(2() ' равен числу способов упорядочения остальных элементов в й различимых транспозиций. Разделив на к(, чтобы сделать этн транс- позиции неразличимыми, получим К сожалению, насколько это известно, такую сумму уже нельзя упростить (если только не прннимагь во внимание использование полиномов Эрмнта 1"2 "гзх х Н„(-1/~~2 ) в качестве отсчетов).
Поэтому, для того чтобы лучше понять поведение величины йо мы применим два косвенных подхода. а) Можно найти производящую функцию г„я"/и! = е'+' 'з Е.- и (42) (см. упр. 25). о) Можно определить асимптотическое поведение величины г„, Это поучительная задача, и ее решение содержит несковько общих методов, которые будут полез- числами (1, 2,..., 15) так, чтобы метка вершины и была меньше метки вершины с, если и -+ е. Иначе говоря, оно равно числу способов топологической сортировки частичного упорядочения (39), как в разделе 2.2.3.
В общем случае можно сформулировать эту же задачу для произвольного ориентированного графа, не содержащего ориентированных циклов. Выло бы хорошо, если бы существовала какая-нибудь простая формула, обобщающая теорему Н дл» произвольного графа, однако не все графы обладают такими приятными свойствами, как графы, соответствующие диаграммам. Другие классы ориентированных графов, для которых задача о разметке вершин имеет простое решение, частично обсуждаются в упражнениях в конце этого раздела.
Там также приводятся упражнения, в которых показано, что для некоторых вариантов ориентированных графов не существует простой формулы, соответствующей теореме Н. Например, число способов разметки вершин не всегда является делителем и(. Завершим наши исследования подсчетом общего числа диаграмм, которые можно сформировать из п различных элементов. Обозначим это число через 1„. Как вытекает нз следствия теоремы В, Ф„равно числу инволюций множества (1, 2,..., и).
Перестановка обратна самой себе тогда н только тогда, когда ее представление с помощью циклов состоит только из единичных циклов (неподвижных точен) н циклов нз двух элементов (транспозиций). Поскольку в г„~ нз г„инволюций (и)— неподвижная точка, а в 1„з из них Ц и) — цикл из двух элементов прн некотором фиксированном г < и, то получаем формулу ны и в связи с другими вопросами; поэтому конец раздела мы посвятим анализу асимптотнческого поведения 1„.
Первый шаг в анализе асимптотического поведения (41) состоит в выделении слагаемых, делающих основной вклад в сумму. Поскольку' 1„(й+ 1) (и — 2я)(и — 2Й вЂ” 1) г„(я) 2(й + 1) можно видеть, что слагаемые постепенно возрастают от Й = 0 до 1„(я + 1) я( 1„(Й), когда я приблизительно равно 1(и — /й ), а затем убывают до нуля, когда х достигает значения, равного примерно 1зи.
Ясно, что основной вклад вносят члены в окрестности значения й = -'(и — ~/й ). Для анализа, однако, удобнее, чтобы основной вклад достигался при значении О, поэтому представим й в виде й= -,'( —,/и)+х (44) и исследуем величину 1„(й) как функцию от х. Чтобы избавиться от факториалов в 1„(я), полезно воспользоваться формулой Стирлинга 1.2.11.2-(18). Для этой цели удобно (как мы вскоре увидим) ограничить область изменения х промежутком «+1/з,с ~ «+г/4 (45) где с равно, скажем, 0.001, тэк что можно включить слагаемое погрешности. После довольно трудоемких вычислений«которые автор в середине бО-х годов выполнил ручкой иа бумаге и которые теперь могут быть реализованы средствами комньютерной алгебры, получается формула З„(й) = ехр( зи 1п и — -'и + ~/й — ~1 1и и — 2хз/ «/й — ( — з 1п я — 1~хз/и+ 2х/~/й+ з(//и — 5~х~/и~/й+ О(из' ~/~)).
(46) Ограничение (45) на х оправдывается тем, что можно положить х = хи'+'/з для получения верхней оценки всех отброшенных слагаемых, а именно е " ехр(1и1пи- 1~и+ ~/й — 11пи — 1 — -'1пт+ О(и ' '/ )). (47) Если же умножить зто на и, получится верхняя оценка суммы исключенных слагаемых. Верхняя оценка имеет меньший порядок, чем те слагаемые, которые вычислим для х в ограниченном промежутке (45), благодаря множителю ехр( — 2из'), намного меньшему любого полинома от и.. Очевидно, можно отбросить в сумме множитель ехр(1и1пи — 1и+ ~/й — -'1пи -1 — 11пх+ ~1/(/й) « (48) после чего нам останется только просуммировать ехр(-2хз/(/й — ззхз/и+ 2х/ /й — -',х4/и4и+ О(из' з/з)) по всем х = а, а+1, ..., б-2, /1-1, где — а и )1 (необязательно целые) равны прибли- зительно и'+'/4. Если сместить интервал суммирования, то формулу суммирования Эйлера (1.2.11.2-(10)) можно записать в виде д 1э /(х) = [ /(х) дх — -/'(х)~ ай~<а а 2 а 1, Г())' Х-'(.)~' + -Вз —,~ + ° + — В,„+), ~ +В +~.
(59) 2 1! ~ ш+1 а Здесь [Вю[ < (4/(2т)'") ['„ф"9(х) [дх. Если положить /(х) = х' ехр(-2хз/ь/й), где 1 — фиксированное неотрицательное целое число, найдем из формулы суммирова- ния Эйлера асимптотический ряд для 1 /(х) прн и -э оо„поскольку у(т1(х) 9-вй/4 1м)( -1/4 ) ( ) с -зэ~ (51) и д(д) — хорошая функция, не зависящая от и. Нроизводная д1"'1(у) равна е ~э, ум- ноженному на полипом от д. Следовательно, /с = 0(пп+' >/4) [ [д1 "й(д) [ дд = 0(пре' >/4).
Далее, поменяв а и (7 на -оо и +со в правой части уравнения (50), мы сведем ошибку к величине, не превышающей 0(ехр( — 2п')) в каждом члене. Таким образом, т' л.|=/ л<и+оь-.) ~... ~о. (52) а<я<а На самом деле при этом конкретном выборе /(х) существен только интеграл! Ин- теграл нетрудно вычислить (см. упр. 26), значит, мы можем выполнить умножение и сложение в формуле (49) и получить «/т/'2(п'/~ — 214п ' '4 + 0(п "/~)), Таким образом, и /з -ч/з+,/ч-~/4(1+ 7 и-Из+ 0(п-з/4)) (53) ч/2 тэ В действительности члены с 0 должны еще содержать дополнительно 9с в экспонен- те, но из наших выкладок ясно, что величина 9< должна исчезнуть, если произвести вычисления с большей точностью. В принципе, этот метод можно расширить и вместо 0(п э/') получить 0(л ь) при любом Й.
Этот асимптотический ряд для 1„ впервые нашли (другим способом) Мозер (Мыег) и Уаймэн (Жушап) [Сапад1аи,7. Маей. Т (1955), 159-1б8[. Метод, использованный прн выводе соотношения (53), представляет собой ис- ключительно полезную методику асимптотнческого анализа, которая была пред- ложена П. С. Лапласом [см. Р. 8. 1,ар!асс, Мешоиеэ Асад. зсй Раг/э (1782), 1-88); она также анализируется в СМасй 29.4 под наименованием чсгад1п8 са11э". Другие примеры и развитие метода, примененного для вывода формулы (53), приводятся в конце раздела 5.2.2.
УПРАЖНЕНИЯ 1. [16[ Какие диаграммы (Р, /3) соответствуют двукстрочному массиву 1 2 3 4 5 6 7 8 91 649571283/ в построении из теоремы А? Какой двухстрочный массив соответствует паре диаграмм 2. (МЯг ) Докажите, что (4, р) принадлежит классу 1 относительно массива (16) тогда и только тогда, когда 1 равно максимальному числу индексов гы..., гп таких, что Р <Р « Р, — Р, йп <ф « ''Оь =д. 3. (М84) Покажите, что соответствие, определенное в доказательстве теоремы А, можно также устаноаитеч построив следующую таблицу: Строка О 5 б 8 Строка 1 О 5 3 Строка 2 оо 9 5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
