3. [М40] Создайте программу определения количества непомеченных свободных деревьев и ориентированных деревьев с п вершинами для п < 100. (Используйте результат упр. 2.) Исследуйте арифметические свойства этих чисел. Что можно сказать об их простых делителях или вычетах по модулю р?

► 4. [НМ39] (Задача Д. Пойа (G. Polya), 1937.) С помощью теории функций комплексного переменного определите асимптотическое значение для количества ориентированных деревьев, выполнив приведенную ниже последовательность действий.

a) Покажите, что существует такое действительное число а от 0 до 1, для которого A{z) имеет радиус сходимости а и A{z) сходится абсолютно для всех таких комплексных z, что \z\ < а, а максимальное значение А{а) - а < оо. [Указание. Если степенной ряд имеет неотрицательные коэффициенты, он либо является целой функцией, либо имеет особую точку на положительной полуоси действительных значений. Покажите, что A{z)/z ограничено при г -> а - 0, используя тождество из упр. 1.]

b) Пусть

F{z, w) = exp (zw + A{z) + 5/1(2) + ---)-w.

Покажите, что F(z,w) в окрестности {z,w) = {a,a/a) является аналитической функцией по каждой переменной в отдельности.

c) Покажите, что в точке {г, w) = (а, а/а) имеем dF/dw = 0, а значит, а = 1.

d) В точке {z,w) = (а, 1/а) покажите, что

к>2

e) Когда \z\ = а я z ф а, покажите, что dF/dw ф О, а, значит, A{z) имеет только одну особую точку- \z\ = а.

f) Докажите, что существует область, большая, чем \z\ < а, в которой

- Aiz) = i - 2/3(1 - z/a) + (1 - z/a)R{z),

где R{z) - аналитическая функция y/z - а. g) Докажите, что в результате этого

ап = ,/т+0(п-а-).

[Замечание. 1/а « 2.955765285652, ау/г w 0.439924012571.]

5. [М25] (Задача А. Кэли (А. Cayley).) Пусть Сп-количество непомеченных ориентированных деревьев с п листьями (т. е. с вершинами с нулевой степенью входа) и по крайней мере двумя поддеревьями во всех других вершинах. Значит, Сз = 2, так как

Найдите формулу для производящей функции, аналогичную (3):

C{z) = J2cnZ. п

6. [М25] Пусть ориентированное бинарное дерево - это такое ориентированное дерево, в котором степень входа каждой вершины - не больше двух. Найдите сравнительно простое

соотношение, которое определяет производящую функцию G{z) для количества различных ориентированных бинарных деревьев с п вершинами, и найдите несколько первых ее коэффициентов.

7. [НМ40] Найдите асимптотическое значение для чисел из упр. 6 (см. упр. 4).

8. [20] Согласно (9) существует шесть свободных деревьев с шестью вершинами. Нарисуйте их и обозначьте вершины-центроиды.

9. [Л/.80], Учитывая тот факт, что центроид может находиться не более чем в одном поддереве свободного дерева, докажите, что в свободном дереве может находиться не более двух центроидов и, более того, что если в таком дереве есть два центроида, то они будут смежными.

► 10. [М22] Докажите, что свободное дерево с п вершинами и двумя центроидами состоит из двух свободных деревьев с п/2 вершинами, которые соединены одним ребром. И наоборот, если два свободных дерева с т вершинами соединить ребром, то получится свободное дерево с 2т вершинами и двумя центроидами.

► 11. [М28] В данном разделе предложена формула (14) для того, чтобы найти количество различных бинарных деревьев с п узлами. Обобщите используемый в разделе метод вывода этой формулы для количества различных <-арных деревьев с п узлами. (См. упр. 2.3.1-35; <-арное дерево либо пусто, либо состоит из корня и t непересекающихся i-арных деревьев.) Указание. Используйте уравнение (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, 6, 5?

14. [10] Справедливо ли такое утверждение: "Последний элемент,/(Vn-i), канонического представления ориентированного дерева всегда является корнем этого дерева" ?

15. [21] Изучите взаимосвязь (если таковая вообще существует) между алгоритмом топологической сортировки из раздела 2.2.3 и каноническим представлением ориентированного дерева.

16. [25] Создайте максимально эффективный алгоритм, который преобразует каноническое представление ориентированного дерева в обычное представление, используемое в компьютере с помощью связей PARENT.

► 17. [М26] Пусть /(х)-целозначная функция, где 1 < /(х) <т для всех целых 1 < X < т. Определим, что х = у, если /(х) = f\y) для некоторого г, s > О, где /°(ж) = х и /""(х) = f{f\x)). Используя методы перечисления, подобные приведенным в этом разделе, покажите, что количество таких функций, что х = у для всех хну, равно m~Q{m), где Q{m) является функцией, которая определена в разделе 1.2.11.3.

18. [24] Покажите, что следующий метод является еще одним способом определения взаимно однозначного соответствия между (п - 1)-кортежами чисел от 1 до п и ориентированными деревьями с п помеченными вершинами. Пусть Vi,..., 14 -листья дерева в порядке возрастания. Пусть {Vi, Vk+i, 14+2, • •, I4) - путь от Vj к корню. В таком случае запишем вершины V,,..., I4+2,14+i. Пусть (V2, 14+2, •. , К)-такой кратчайший ориентированный путь от V2, что 14 уже выписана. Затем выпишем К, • , I4+2,14+1. Далее пусть (V3,14+1, • •, 14)-такой кратчайший ориентированный путь от V3, что Vs уже выписана. После этого выпишем Vs,... ,Vr+i и т. д. Например, дерево (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. [М;8.] (Задача Дж. Риорвана (J. Riordan).) Сколько существует различных помеченных ориентированных деревьев с п вершинами, из которых ко вершин имеют нулевую степень входа, ki -степень входа 1, /гг - степень входа 2, ... ? (Обратите внимание, что обязательно выполняются условия /го -I- A:i -I- /гг -I- • • • = n и A:i -I- 2/гг -I- 3/гз + = п - 1.)

► 21. [М21 ] Перечислите все помеченные ориентированные деревья, вершины которых имеют степень входа 0 или 2. (См. упр. 20 и 2.3-20.)

22. [Л/.80] Сколько существует помеченных свободных деревьев с п вершинами? (Иначе говоря, используя п вершин, можно построить 2(2) графов в зависимости от того, какие из (2) возможных ребер используются в графе. Сколько среди них таких графов, которые являются свободными деревьями?)

23. [М21] Сколько упорядоченных деревьев можно построить с помощью п помеченных вершин? (Предложите простую формулу на основе факториалов.)

24. [М/б] Все помеченные ориентированные деревья с вершинами 1-4 и корнем 1 показаны в виде схемы (15). Сколько можно получить помеченных упорядоченных деревьев с этими вершинами и этим корнем?

25. [М20] Чему равно значение r{n,q) из уравнений (18) и (19)? (Предложите явную формулу, так как в данном разделе упоминается только соотношение г{п, п - 1) = п"~.)

26. [20] На основе определения, приведенного в конце этого раздела, создайте ((3,2,4), (1, 4, 2))-схему, аналогичную схеме (23), и найдите число к, которое соответствует каноническому представлению с i = 8, последовательностям цветов "красный, желтый, синий, красный, желтый, синий, красный, синий, синий" и "красный, желтый, синий, желтый, желтый, синий, желтый" и последовательностям чисел 3; 1, 2, 2, 1; 2, 4.

► 27. [М28] Пусть Ui,U2, ,Up,... ,Uq; Vi, Кг, •.., К -вершины ориентированного графа, где 1 < р < q. Пусть / - некоторая функция на множестве {р + 1,... ,q} с областью значений {1,2,...,г}и пусть ориентированный граф содержит в точности q - р дуг от Ui, к V/(jt) для р < к < q. Покажите, что количество способов добавления г дополнительных дуг по одной от каждой вершины V к каждой вершине U, таких, что полученный в результате ориентированный граф не содержит ориентированных циклов, равно q~p. Обобщая метод канонического представления, докажите это, т. е. установите взаимно однозначное соответствие между всеми такими способами добавления г дополнительных дуг и множеством всех последовательностей целых чисел ааг,...где 1 < а*, < 9 для 1<к<ги1<аг<р.

28. [М22] {Двусторонние деревья.) Используйте результат упр, 27 для перечисления таких помеченных свободных деревьев с вершинами U\, Um, Vi, Vn, в которых все ребра проведены от Uj к Vk для определенных j и к.

29. [НМ26] Докажите, что если Ek(r,t) = r{r + kt)~/k\ и гх = Inx, то

x- = £:,(r,<)z=

к>0

для фиксированного t и для достаточно малых \z\ и х - 1. [Используйте тот факт, что Gmiz) = Gi{z)" в рассуждениях, приведенных после уравнения (19).] В этой формуле г обозначает произвольное действительное число. [Замечание. Как следствие этой формулы получим тождество

J2Ekir,t)En-k{s,t) = En{r + s, t),