AOP_Tom3 (1021738), страница 33
Текст из файла (страница 33)
Итак, мы получили результат, который в работе Я. Б. ггшпе, С. де В. Но1ппэоп, В.. М. Тога!1, Сапаойэл л. МаНь 6 (1954), 316-324, сфомулирован в виде теоремы. Теорема Н. Количество диаграмм данной формы, сосзввлеэтых из элементов (1, 2,..., о) „равно п1, деленному на произведение длин уголков. $ Такая лаконичная формулировка заслуживает и лаконичного доказательства. Мы приведем нестрогое рассуждение, основанное на эвристике. Каждый элемент диаграммы — минимальный в своем уголке; если заполнить клетки диаграммы случайным образом, то вероятность того, что в клетке (1, 1) окажется минимальный элемент соответствующего уголка, есть величина, обратная длине уголка.
Перемножение этих вероятностей по всем 1 и у приводит к формулировке теоремы Н. Однако такое рассуждение ошибочно, поскольку эти события отнюдь не являются независимыми! Все известные доказательства теоремы Н, основанные на комбинаторных свойствах уголков, были некорректны вплоть до 1992 года (см.
упр. 39), хотя и предлагалось несколько непрямых доказательств (см. упр. 35, 36 и 38). Существует интересная связь между теоремой Н и перечислением деревьев, которое рассматривалось в главе 2.Мы видели, что бинарным деревьям с о узлами соответствуют перестановки, которые можно получить с помощью стека, и что этим перестановкам соответствуют последовательности аэ аэ...
ат„п литер Б и и литер Х, такие, что количество литер Б никогда не бывает меньше количества литер Х, если читать последовательность слева направо (см. упр. 2.2.1 — 3 и 2.3.1 — 6). Подобным последовательностям естественным образом сопоставляются диаграммы формы (о,о); в 1-ю строку помещаются индексы 1, такие, что а; = Б, а во 2-ю строку — индексы, при которых а; = Х. Например, последовательности БББХХББХХБХХ соответствует диаграмма (37) Условие, налагаемое на столбцы, удовлетворяется в такой диаграмме в том и только том случае, когда прн чтении слева направо число литер Х никогда не превышает числа литер Б.
По теореме Н количество всевозможных диаграмм формы (п,п) равно (2п)! (и+ 1)! и! следователыю, таково же число бинарных деревьев, что согласуется с формулой 2.3.4.4- (14). Более того, если воспользоваться диаграммой формы (и, гп) при п > пз, то при помощи этого рассуждения можно решить и более общую "задачу о баллотировке", рассмотренную в ответе к упр. 2.2.1-4. Таким образом, теорема Н в качестве простых частных случаев включает в себя некоторые весьма сложные задачи о перечислении. Всякой диаграмме А формы (и, и) из элементов 11, 2,..., 2п) соответствуют две диаграммы (Р, 1~) одинаковой формы.
Следующий способ построения такого соответствия предложен Мак-Магоном ]СотЬша1огу Апа!уэи 1 (1915), 130 — 131]. Пусть Р состоит из элементов 11,...,и), расположенных так, как в А, а Я получается, если взять остальные элементы А, повернуть всю конфигурацию на 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 6 (38) (39) Наоборот, каждой паре диаграмм одинаковой формы, состоящих из и элементов и из не более чем двух строк, соответствует диаграмма формы (и, и). Следовательно (из упр. 7), число перестановок а~ аэ...
а„множества 11, 2,..., и), не содержащих убывающих подйоследовательностей а, > а > аь прн 1 < 1 < й, равно числу бинарных деревьев с и узламя. Интересное взаимно однозначное соответствие между такими перестановками и бинарными деревьями, установленное более прямым способом, чем тот окольный путь через, алгоритм 1, которым воспользовались мы, нашел Д. Ротем [см. П.
Ногеш, 1пГ. Ргос. Ееггегэ 4 (1975), 58 — 61]; аналогично существует довольно прямое соответствие между бинарными деревьями и перестановками, пе содержащими подпоследовательностей а. > аь > а; при 1 < 1 < й (см. упр. 2.2.1 — 5). Число способов заполнения диаграммы формы (6,4,4,1), очевидно, равно числу способов разметки вершин ориентированного графа числами (1,2,..., 15) так, чтобы метка вершины и была меньше метки вершины е, если и -> е.
Иначе говоря, оно равно числу способов топологической сортировки частичного упорядочения (39), как в разделе 2.2.3. В общем случае можно сформулировать эту же задачу для произвольного ориентированного графа, не содержащего ориентированных циклов. Было бы хороню, если бы существовала какая-нибудь простая формула, обобщающая теорему Н для произвольного графа, однако не все графы обладают такими приятными свойствамн, как графы, соответствующие диаграммам. Другие классы ориентированных графов, для которых задача о разметке вершин имеет простое решение, частично обсуждаются в упражнениях в конце этого раздела. Там также приводятся упражнения, в которых показано, что для некоторых вариантов ориентированных графов нс существует простой формулы, соответствующей теореме Н. Например, число способов разметки вершин не всегда является делителем и!.
Завершим наши исследования подсчетом общего числа диаграмм, которые можно сформировать из и различных элементов. Обозначим это число через 1„. Как вытекает из следствия теоремы В, С„равно чиглу инволюций множества (1, 2,..., и). Перестановка обратна самой себе тогда и только тогда, когда ее представление с помощью циклов состоит только из единичных циклов (неподвижных точек) и циклов из двух элементов (транспозиций). Поскольку в Са ~ из 1„инволюций (и)— неподвижная точка, а в с„т из них (у и) — - цикл из двух элементов при некотором фиксированном у < ~, то получаем формулу (40) которую вывел Роте в 1800 годудля получения таблицы значений с„при малых и. Значения для и > 0 равны 1, 1, 2, 4, 10, 26, 76, 232, 764, 2 620, 9 496, ....
Рассмотрим другой способ. Пусть имеется й циклов из двух элементов и (п — 2й) единичных циклов. Существует (",) способов выбора неподвижных точек, и полиномиальпый коэффициент (2к)!/(2!) ' равен числу способов упорядочения остальных элементов в к различимых транспозиций. Разделив на 1с!, чтобы сделать эти транс- позиции неразличимыми, получим К сожалению, насколько зто известно, такую сумму уже нельзя упростить (если только не принимать во внимание использование полиномов Эрмита 1"2 "~эх хВ а( — 1/~/2) в качестве отсчетов). Поэтому, для того чтобы лучше понять поведение величины 1„, мы применим два когвенных подхода.
а) Можно найти производящую функцию (42) (см. упр. 25). Ъ) Можно определить асимптотическое поведение величины 1„. Это поучительная задача, и ее решение содержит несколько общих методов, которые будут полез- ны и в связи с другими вопросами; позтому конец раздела мы посвятим анализу асимптотического поведения ! . Первый шаг в анализе асимптотического поведения (41) состоит в выделении слагаемых, делающих основной вклад в сумму.
Поскольку 1„(/4 + 1) (п — 2й) (и — 2/4 — 1) 1„(А) 2(/с + 1) можно видеть, что слагаемые постепенно возрастают от к = 0 до !„(й + 1) 1„(/4), когда й приблизительно равно, (и —,/и ), а затем убывают до нуля, когда к достигает значения, равного примерно -'и. Ясно, что основной вклад вносят члены в окрестности значения Й = -'(и — ~/и ). Для анализа, однако, удобнее, чтобы основной вклад достигался при значении О, позтому представим й в виде 2( «/ )+ и исследуем величину г„(/4) как функцию от х. Чтобы избавиться от факторивлов в 1„(й), полезно воспользоваться формулой Стирлинга 1.2.11.2-(18). Для втой цели удобно (как мы вскоре увидим) ограничить область изменения х промежутком «-~-1/4 С ~, «Ы/4 (45) (44) 4 хз/и+ 2х/ д+ 1/ / 4х4/и / + О(пз з/4)).
(40) Ограничение (45) на х оправдывается тем, что можно положить х = хп'+'/4 для получения верхней оценки всех отброшенных слагаемых, а именно е з" ехРЯп!пп — зп+ «/и — -'1пп — ~1 — 1 !пк+0(п~' /4)) . (47) Если же умножить это на и, получится верхняя оценка суммы исключенных слагаемых. Верхняя оценка имеет меньший порядок, чем те слагаемые, которые вычислим для х в ограниченном промежутке (45), благодаря множителю ехр( — 2пз'), намного меньшему любого полннома от и..
Очевидно, можно отбросить в сумме множитель ехр(зп!пп — зп+ «/и — 4 !пп — 4 — з !пк+ з/'«/п), (48) после чего нам останется только просуммировать ( 2 з/ /- 4, з/ + 2 / /- 4 4/ /- + О( з -3/4)) =ехр 1 — — — + — — 1+2 — +2— (1 — — — ~ (1«««( " '«)«(«9) 3 п~/и/ где е равно, скажем, 0.001, так что можно включить слагаемое погрешности. По4ле довольно трудоемких вычислений, которые автор в середине 60-х годов выполнил ручкой на бул4аге и которые теперь могут быть реализованы средствами компьютерной алгебры, получается формула ~««(/4) схр(зп!пп за+ ъ/и 4 !пп 2х /1/и 4 з !як по всем х = сг, и+1, ..., 8 — 2, 8-1, где — а и 8 (необязательно целые) равны прибли- зительно и'+'7». Если сместить интервал суммирования, то формулу суммирования Эйлера (1.2.11.2 — (10)) можно записать в виде д 7'(х) = / 7" (х) дх — -7'(х) 2 « д а 1 7'(х) ) 1 ~~ ~(х) + -Вг ~ + + Вгях» + Вт».» (50) 2 1! ~ т+1 т! Здесь [В»„[ < (4/(2к) ) [ [~1~~(х)[дх.
Если положить |(х) = х'ехр( — 2хг/»7п), где 1 — фиксированное неотрицательное целое число, найдем из формулы суммирова- ния Эйлера асимптотический ряд для 2 7(х) при и -+ со, поскольку У("'~(х) = пй Рчд~т~(п пмх), д(д) д»е-гэ' . (51) и д(9) — хорошая функция, не зависящая от п. Производная д~™й(д) равна е гэ, ум- ноженному на полипом от у.
Следователь»ю, В,„= 0(пр»' Лм) [ т [д~"6(д)/дд = 0(пр ы ~/»). Далее, поменяв сг и 8 на -оо и +со в правой части уравнения (50), мы сведем ошибку к величине, не превышающей 0[ехр( — 2п')) в каждом члене. Таким образом, 7'(х) = / 7(х)дх+0(п "') для всех т > О. (52) а<я<В На самом деле при этом конкретном выборе 7'(х) существен только интеграл! Ин- теграл нетрудно вычислить (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
