AOP_Tom1 (1021736), страница 112
Текст из файла (страница 112)
2.3.4,2-7 является ориентированным деревом. Ясно, что последовательность хы яэ,..., я„~ тождественна последовательности (16) для этого ориентированного дерева. Так как данный процесс является обратимым, получим взаимно однозначное соответствие между кортежами из (п — 1) чисел последовательности (1,2,...,п) и ориентированными деревьями с этими вершинами. Следовательно, существует и" различных ориентированных деревьев си помеченными вершинами.
Если выбрать в качестве корня какую-либо одну вершину, причем безразлично, какую именно, то будет существовать п" э различных ориентированных деревьев с корнем, выбранным (1,2,...,п). Для (15) это дает в итоге 16 = 44 э деревьев. Теперь легко определить количество свободных деревьев с помеченными вершинами (см. упр. 22). Количество упорядоченных деревьев с помеченными вершинами также легко подсчитать, если известен ответ для аналогичной задачи без помеченных вершин (см.
упр. 23). Итак, задачи перечисления для трех фундаментальных классов деревьев с помеченными и непомеченными вершинами решены. Интересно было бы узнать, что дает обычный метод производящих функций для решения задачи перечисления помеченных ориентированных деревьев. Для этого, вероятно, проще всего было бы рассмотреть величину г(п,у), т. е. количество помеченных ориентированных графов с и вершинамн и без ориентированных циклов, причем из д помеченных вершин этих графов выходит по одной дуге.
Следовательно, количество помеченных ориентированных деревьев с указанным корнем равно г(п, и — 1). На основе таких обозначений и за счет простого подсчета аргументов получим, что для любого фиксированного целого числа т г(п,у) = ~ ~ ) г(гп+Й,И)г(п — т — lс, д — й), если О < т < п — 9, ~9~ г(п,у) = ~( )г(п — 1, д — Й), /9~ если д = п — 1. (18) (19) Вид этих соотношений указывает на то, что в данном случае можно было успешно использовать производящую функцию: С„,(г) = г(т,О)+г(т+1, 1)х+,' + . = ~~' г(т + 2, 2)х~ г(М + т, Й)г" С помощью соотношения (18) получим С„-ч(з) = С (х)бд-д-т(х) и, следовательно, с помощью метода индукции по т получим Сп,(х) = С~(з) . Затем из соотношения (19) получим г(п, п — 1)х" ~ г(п — 1, п — 1 — к)х" 01(г) = ~ (п — 1)! Й! (п — 1 — Й)! ,~ (зС1(з)) ., < 1 И ь>а ь —,Сь(х) ь>о Первое из этих соотношений получается, если разбить непомеченные вершины на две группы, А и В, с т вершинами в А и п — 9 — т вершинами в В.
Затем д помеченных вершин разобьем на к вершин, с которых начинаются пути, ведущие в А, и д — й вершин, с которых начинаются пути, ведущие в В. Соотношение (19) получается, если рассмотреть ориентированные деревья, в которых корень имеет степень Й, Иначе говоря, для Сг (г) = ю решение этой задачи заключается в поиске коэффициентов решения такого трансцендентного уравнения: (20) ю = е' Это уравнение можно было бы решить с помощью формулы обращения Лагранжа следующим образом. Из г = с,/7'(~) следует, что (21) где Ул(ь) = г'(ь)". если г' — аналитическая функция в окрестности нуля и ((О) ф 0 (см.
упр. 4.7 — 16). В данном случае, предполагая, что ~ = гю, 7'(~) = еб, получим (и + 1)" и! пйб (22) что полностью соответствует приведенному выше решению, Дж. Н. Рейни (С. Х, Вапеу) показал, что этот метод можно применить и для решении уравнения более общего вида ю = уге" + уге"" + + у,е * и = (им пг,..., пе) и запишем для удобства 2:п=пг+пг+ .+и,. Предположим, что имеется а цветов Сы Сг,..., С„и рассмотрим ориентированные графы, каждой вершине которых присвоен определенный цвет, например 7 Кр иый б Желтый 1 Синий г (23) Красный Пусть т(п,с1) — количество таких способов проведения дуг и присвоения цветов вершинам (1,2,..., и), что 1) для 1 < 1 < э существует в точности и, вершин с цветом С; (следовательно, и= Еп); й) существует 4 дуг, которые выходят по одной из каждой вершины (1, 2,..., 4); ш) для 1 < г < а существует в точности де дуг, проходящих из вершин с цветом С; (следовательно, д = ) е1); 1у) не существует ориентированных циклов (следовательно, д < и за исключением случая, когда д = п = О).
Назовем это (п,е1)-построениекь представив ю в виде степенного ряда по ры...,у, и гы...,г,. Для этого общего случая рассмотрим е-мерные векторы целых чисел Например, если С1 — красный цвет, Сг — желтый цвет и Сг — голубой цвет, то (23) схематично представляет ((3, 2, 2), (1, 2, 2))-построение. При наличии только одного цвета получим уже решенную задачу для ориентированного дерева. Идея Рейни заключалась в обобщенйи одномерного построения до г размерностей.
Пусть и и с1 — фиксированные г-мерные векторы неотрицательных целых чисел, а и = 2.п, 4 = Ец. Для каждого (п,с1)-построения и каждого числа Й, 1 < Й < и, определим каноническое представление, которое состоит из следующих четырех компонентов: а) числа 1, д < г < и; Ь) последовательности п цветов, в которой присутствует п, цветов С;; с) последовательности 4 цветов, в которой присутствует ал цветов С,; 6) последовательности цг элементов множества (1,2,...,п;) для 1 < 1 < г.
Это каноническое представление определяется следующим образом. Сначала перечислим вершины (1,2,...,д) в порядке ЪИ7~,....,И канонического представления ориентированных деревьев (как определено выше), а затем запишем под вершиной Ъд номер вершины У(Ъ" ) на дуге, проходящей от 1'. Пусть 1 = ДЪ~), а последовательность цветов (с) соответствует цветам вершин 7(ь|),...,1(Гд). Пусть последовательность цветов (Ь) соответствует цветам вершин 1с, й + 1,..., п, 1,..., 1г — 1.
Наконец, пусть 1-я последовательность (о) равна хп,хп,..., х,, где хи = т, если ~-й элемент цвета С, последовательности 1(1'1),..., Д$') является т-м элементом цвета С; последовательности й, й + 1, ..., п, 1, ..., й — 1. Например, рассмотрим графы (23) и допустим, что Ь = 3. Начнем с перечисления вершин 1 ы...,1ь и (Я),..., Д1г) и номеров под ними: 1 2 4 5 3 7 6 3 3 6 Значит, г = 6, а последовательность (с) представляет соответственно цвета вершин 7, 6, 3, 3, 6, а именно — красный, желтый, синий, синий, желтый. Последовательность (Ь) представляет соответственно цвета вершин 3, 4, 5, 6, 7, 1, 2, а именно— синий, желтый, красный, желтый, красный, синий, красный.
Наконец, чтобы получить элементы такого цвета, нужно составить следующую таблицу. Элементы такого цвегаа среди 3,4,5,6,7,1,2 5,7,2 4,6 3,1 Шив5равание столбца Я с помощью столбца 2 2 Элементы тахаев цвета среди 7,6,3,3,6 7 6,6 3,3 Цвет Красный Желтый Синий 2,2 1,1 Итак, искомыми последовательностями типа (6) будут 2; 2, 2 и 1, 1.
На основе такого канонического представления можно восстановить исходное (и г4)-построение и число к', поступив следующим образом. Исходя из (а) н (с) узнаем цвет вершины б Последний элемент последовательности (с1) с таким цветом в сочетании с (Ь) позволяет узнать расположение числа 1 в последовательности й,...,п,1,...,Й вЂ” 1. Таким образом, узнаем значения й и цветов всех вершин. Тогда последовательности (с1) вместе с (Ь) и (с) определят (Я),7(1г), П1р) и наконец ориентированный граф будет полностью восстановлен после определения расположения Ъ'!,..., С'е так, квк это было сделано для ориентированных деревьев.
Обратимость подобного канонического представления позволяет подсчитать количество возможных (п,Ч)-построений, поскольку существует и — д вариантов для (а), вариантов для (о), вариантов для (с) и и!и птп... пт" вариантов для (Й), которые выражены в виде полиномиальных коэффициентов. Общий результат найдем, разделив произведение полученных величин на и: и — д и! !7! г(п, Ч) = ям н~'... и . (24) и и1! ц,! 4!К,Ь! ! 2'" е' Кроме того, можно получить аналогичные (18) и (19) соотношения: ) т(С, 1() г(п — С, Ч вЂ” 1с), если 0 < гп ( ~;(и — Ч), (25) с ~Чз г(п,с1) = Е(е — к1=п~ при условии, что г(0,0) = 1 и г(п, Ч) = О, если значение и! или 4, отрицательно либо если е > и; г(и,Ч) = ~ ~~ 1 у! г(п — е„Ч вЂ” ке!), если ~п = 1+ ~Ч, (26) ~=! ь Теорема К (Сеогйе Х.
Капеу, Сапа!(!ап 7. Ма(1!. 16 (1964), 755-762). Пусть !"(и Ч) ь1 е, и д, !в= ~ — у '...у,'з '...г,', (7..Ч) ! Е( -~1=! (27) где г(п, Ч) определяется формулой (24), а и, Ч вЂ” и-меряые целочвсленные векторы. Тогда !в удовлетворяет тождеству (28) !в = у!е" + рте" + +у,е' Доказа!пельсгпео. С помощью (25) и метода индукции по тп получим, что (29) где е; — вектор с единицей в позиции ! и нулями в остальных позициях. Соотношение (25) основано на разбиении вершин (!7 + 1,..., и) на две части с гп и и — д — гп элементами в каждой. Второе соотношение получается за счет удаления единственного корня и рассмотрения оставшейся после этого структуры. Рассмотрим теперь следующий результат.
3. [М40) Создайте программу определения количества непомеченных свободных деревьев и ориентированных деревьев с п вершинами для и < 100. (Используйте результат упр. 2.) Исследуйте арифметические свойства этих чисел. Что можно сказать об их простых делителях или вычбтах по модулю р? 4. [НМ39] (Задача Д. Пайа (С. Рб!уа), 1937.) С помощью теории функций комплексного переменного определите асимптотическое значение для количества ориентированных деревьев, выполнив приведенную ниже последовательность действий. а) Покажите, что существует таксе действительное число а от 0 до 1, для которого А(г) имеет радиус сходимости а и А(г) сходится абсолютно для всех таких комплексных з, что ]х] < а, а максимальное значение А(а) = а < са, [Указаное. Если степенной ряд имеет неотрицательные коэффициенты, он либо является целой функцией, либо имеет особую точку на положительной полуоси действительных значений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
