AOP_Tom1 (1021736), страница 113
Текст из файла (страница 113)
Покажите, что А(г)/г ограничено при в -э а — О, используя тождество из упр. 1.] Ь) Пусть Р(г ю) = ехр(зю+ гА(г ) + зА(х ) + " ') Покажите, что Г(в, ю) в окрестности (в, ш) = (а, а/а) является аналитической функцией по каждой переменной в отдельности. с) Покажите, что в точке (г, ю) = (а, а/а) имеем ду /дш = О, а значит, а = 1. в!) В точке (хв ю) = (а, 1/а) покажите, что дег а — =а, дю' е) Когда ]г) = а и г ~ а, покажите, что дГ/дю ~ О, а значит, А(г) имеет только одну особую точку — [г] = а. 1) Докажите, что существует область, ббльшая, чем [г] < а, в которой где Л(з) — аналитическая функция в/г — а. 8) Докажите, что в результате зтога а„=, з/д/2лл+ 0(п эюа ") [Замечамае.
1/а ш 2.955765285652, ав/д/2л вв ОА39924012571.] 5. [М25] (Задача А. Кэпи (А. Сау!еу).) Пусть с„— количество непомеченных ориентированных деревьев с и листьями (т. е. с вершинами с нулевой степенью входа) и по крайней мере двумя поддеревьялви во всех других вершинах. Значит, сз = 2, так как Найдите формулу для производящей функции, аналогичную (3) С(г) = ~с г" 6. [М85) Пусть ориентированное бинарное дерева — зто такое ориентированное дерево, в котором степень входа каждой вершины — не больше двух.
Найдите сравнительно простое соотношение, которое определяет производящую функцию С(е) для количества различных ориентированных бинарных деревьев с п вершинами, и найдите несколько первых ее коэффициентов. Т. [НМ40] Найдите асимптотическое значение для чисел из упр. 6 (см, упр, 4). 8. [20] Согласно (9) существует шесть свободных деревьев с шестью вершинами.
Нарисуйте их и обозначьте вершины-центроиды. 9. [М20], Учитывая тат факт, что центроид может находиться не более чем в одном поддереве свободного дерева, докажите, что в свободном дереве может находиться не более двух центроидов и, более того, что если в таком дереве есть два цеитроида, то они будут смежными. ь 10. [М22] Докажите, что свободное дерево с и вершинами и двумя центроидами состоит из двух свободных деревьев с и/2 вершинами, которые соединены одним ребром. И наоборот, если два свободных дерева с гл вершинами соединить ребром, то получится свободное дерево с 2т вершинами и двумя центроидал»»». ь 11. [М86] В данном разделе предложена формула (14) для того, чтобы найти количество различных бинарных деревьев с и узлами.
Обобщите используемый в разделе метод вывода этой формулы для количества различных барных деревьев с и узлами. (См. упр, 2.3.1 — 35; 1-арное дерево либо пусто, либо состоит из корня и 1 непересекающихся 1-арных деревьев.) Указание. Используйте уравнение (21) из раздела 1.2.9. 12. [М20] Найдите количество помеченных ориентированных деревьев с п вершинами, используя детерминанты и результат упр. 2.3.4.2 — 19. (См. также упр.1.2.3-36,) 13. [15] Какое ориентированное дерево с вершинами [1,2,..., 10) имеет такое каноническое представление: 3, 1, 4, 1, 5, 9, 2, б, 5? 14. [10] Справедливо ли такое утверждение: "Последний элемент, 1(!'„» ), канонического представления ориентированного дерева всегда является корнел» этого дерева"? 15.
[21] Изучите взаимосвязь (если таковая вообще существует) между алгоритмом топологической сортировки из раздела 2.2.3 и каноническим представлением ориентированного дерева. 16. [25] Создайте максимально эффективный алгоритм, который преобразует каноническое представление ориентированного дерева в обычное представление, используемое в компьютере с помощью связей РЫЕМТ. ° 17. [М20] Пусть 1(х) — целозначная функция, где 1 < 1(х) <»и для всех целых 1 < х <»и.
Определим, что к е— в у, если гй»(х) = 1(д»(р) для некоторого г, в ) О, где »»"'(х) = г. и ? '+ (х) = з (1 " (х)). Используя методы перечисления, подобные приведенным в этом разделе, покажите, что колнчество таких функций, что х: — у для всех х и 9, равно т~ 'О(т), где Я(т) является функцией, которая определена в разделе 1.2.11.3. 18. [24] Покажите, что следующий метод является еще одним способом определения взаимно однозначного соответствия между (п — 1)-кортежами чисел от 1 до и и ориентированными деревьями с и помеченными вершинами. Пусть !'»...., !'ь — листья дерева в порядке возрастания. Пусть (!», !»ьэ», !»ьдд,..., 1») — путь от !г» к корню.
В таком случае запишем вершины 1»..., 1~»дд, !»»~». Пусть (!э, !» э», !»дэд,, !6) — такой кратчайший ориентированный путь от !гд, что Г уже выписана. Затем выпишем !'„..., !д» ю !'д Далее пусть ((з, И э»,... !',) — такой кратчайший ориентированный путь от 1'з, что Г, уже выписана. После этого вь»пишем !'„..., !'„.~» и т.
д, Например, .дерево (17) могло бы быть выписано в таком виде: 3, 1, 3, 3, 5, 10, 5, 10, 1. Покажите, что этот процесс является обратимым, в частности нарисуйте схему ориентированного дерева с вершинами (1,2,...,10) и представлением 3. 1, 4, 1, 5, 9, 2, 6, 5. 19. [М24] Сколько существует различных помеченных ориентированных деревьев с и вершинами, среди которых я являются листьями (т. е, имеют нулевую степень входа)? 20.
[М24] (Задача Дж. Риордана (Л. Вйогбап).) Сколько существует различных помеченных ориентированных деревьев с и вершинами, из которых ко вершин имеют нулевую степень входа, (г~ †степе входа 1, кэ †степе входа 2, ...? (Обратите внимание, что обязательно выполняются условия йо+ й~ + яг+ = пи /с~ + 2яэ+ Зяз+ . = п — 1.) ь 21. [М21] Перечислите все помеченные ориентированные деревья, вершины которых имеют степень входа 0 или 2. (См. упр. 20 и 2.3-20.) 22.
[М20] Сколько существует помеченных свободных деревьев с и вершинами? (Иначе говоря, используя и вершин, можно построить 2(э) графов в зависимости от того, какие из (") возможных ребер используются в графе. Сколько среди них таких графов, которые являются свободными деревьями?) 23. [М21] Сколько упорядоченных деревьев можно построить с помощью п помеченных вершин? (Предложите простую формулу на основе факториалов.) 24. [М16] Все помеченные ориентированные деревья с вершинами 1 — 4 и корнем 1 показаны в виде схемы (15). Сколько можно получить помеченных упорядоченнмя деревьев с этими вершинами и этим корнем? 20.
[М20] Чему равно значение г(п,9) из уравнений (18) и (19)? (Предложите явную формулу, так как в данном разделе упоминается только соотношение г(п, п — 1) = и" '.) 26. [90] На основе определения, приведенного в конце этого раздела, создайте ((3,2,4), (1, 4,2))-схему, аналогичную схеме (23), и найдите число й, которое соответствует каноническому представлению с 1 = 8, последовательностям цветов "красный, желтый, синий, красный, желтый, синий, красный, синий, синий" и 'красный, желтый, синий, желтый, желтый, синий, желтый" и последовательностям чисел 3; 1, 2, 2, 1; 2, 4. ь 27. [Мйй] Пусть Ум(Гэ,..., Ую..., С'; Рм Гю..., 19 —.
вершины ориентированного графа, где 1 < р < 9. Пусть 1 — некоторая функция на множестве (р+1,...,д) с областью значений [1, 2,..., г) и пусть ориентированный граф содержит в точности 9 — р дуг от Сь к $'ПЮ Дпя р < я' < 9. Покажите, что количество способов добавления г дополнительных дуг по одной от каждой вершины 1' к каждой вершине У, таких, что полученный в результате ориентированный граф не содержит ориентированных циклов, равно 9" 'р. Обобщая метод канонического представления, докажите это, т. е. установите взаимна однозначное соответствие между всеми такими способами добавления г дополнительных дуг и множеством всех последовательностей целых чисел омам...,а„, где 1 < аь < 9 для 1<я<ги1<а„<р. 26.
[М22] (Двусторонние деревья.) Используйте результат упр. 27 для перечисления таких помеченных свободных деревьев с вершинами бм ..., П, 1'м, И, в которых все ребра проведены от У~ к 1'э для определенных г' и й. 29. [НМйб] Докажите, что если Еь(г,1) = г(г + яг) " '/Ы и гх' = 1и х, то я" = ~ Еь(г,г)г для фиксированного 1 и для достаточно малых [я[ и [г — 1[.
[Испсшьзуйте тот факт, что С (г) = С~(г) в рассуждениях, приведенных после уравнения (19).] В этой формуле г обозначает произвольное действительное число. [Замечание. Как следствие этой формулы получим тождество Еь(г,1)Е„э(в,г) = Е„(г+ в, 1), э=о из которого следует биноллиадьная теорема Абеля, см. (16) в разделе 1.2.б. Ср. также с (30) из того же раздела.[ 30. [МЗУ) Пусть и, х, у, хц... х — положительные целые числа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
