(tree mapping), если f"}(x), т. е. выполненная п раз итерация f {/(• (f(x)) )) этой функции равна 1 для всех х. Сколько в таком случае существует отображений дерева?". Эта задача возникает, например, в связи с генерированием случайных чисел. К большому удивлению, можно обнаружить, что в среднем точно одна из каждых п таких функций / является отображением дерева.

Можно легко решить задачу перечисления с помощью общих формул для подсчета поддеревьев графа, которые получены в предыдущих разделах (см. упр. 12). Однако существует и более информативный способ решения, который позволяет получить новый и компактный метод представления ориентированной древовидной структуры.

Предположим, что дано ориентированное дерево с вершинами {1,2, ...,п} и дугами п - 1, которые проходят от j к f{j) для всех j, за исключением корня. В нем существует по крайней мере одна концевая вершина (лист), поэтому предположим, что Vi -наименьший номер листа. Если п > 1, запишем f(Vi) и удалим из дерева вершину Vi и дугу Vi -> f(Vi). Пусть V2-наименьший номер листа, который получился в результате предыдущей операции. Если п > 2, запишем /(V2) и удалим вершину V2 и дугу V2 -> /(V2) из дерева, а затем будем продолжать в таком духе до тех пор, пока из данного дерева не будут удалены все вершины, кроме корня. Таким образом получим последовательность из п - 1 чисел

fivi), f(V2),f(v„-i), 1 < т) < п, (16)

которая называется каноническим представлением (canonical representation) исходного ориентированного дерева.

Например, ориентированное дерево

(17)

XI о

б«

с 10 вершинами имеет такое каноническое представление: 1, 3, 10, 5, 10, 1, 3, 5, 3.

Важной особенностью здесь является возможность обращения данного процесса и перехода от рассмотрения произвольной последовательности из п - 1 чисел (16) к рассмотрению ориентированного дерева, которое порождает эту последовательность. Действительно, рассмотрим произвольную последовательность Xi, Х2, ..., Хп-1 чисел от 1 до п. Пусть Vi - это наименьшее число, которое не представлено в последовательности xi,..., Xn-i, а V2 -это наименьшее число ф Vi, которое не представлено в последовательности Х2,. . ,Xn-i и т. д. Получив, таким образом, перестановку V1V2 . - Vn целых чисел {1,2,..., п}, проведем дуги от вершины Vj к вершине Xj для 1 < j < п и получим ориентированный граф без ориентированных циклов, который согласно результату упр. 2.3.4.2-7 является ориентированным деревом. Ясно, что последовательность xi,X2, ,Xn-i тождественна последовательности (16) для этого ориентированного дерева.

Так как данный процесс является обратимым, получим взаимно однозначное соответствие между кортежами из (п - 1) чисел последовательности {1,2,..., п} и ориентированными деревьями с этими вершинами. Следовательно, существует п""

различных ориентированных деревьев с п помеченными вершинами. Если выбрать в качестве корня какую-либо одну вершину, причем безразлично, какую именно, то будет существовать п"" различных ориентированных деревьев с корнем, выбранным {1,2,..., п}. Для (15) это дает в итоге 16 - 4~ деревьев. Теперь легко определить количество свободных деревьев с помеченными вершинами (см. упр. 22). Количество упорядоченных деревьев с помеченными вершинами также легко подсчитать, если известен ответ для аналогичной задачи без помеченных вершин (см. упр. 23). Итак, задачи перечисления для трех фундаментальных классов деревьев с помеченными и непомеченными вершинами решены.

Интересно было бы узнать, что дает обычный метод производящих функций для решения задачи перечисления помеченных ориентированных деревьев. Для этого, вероятно, проще всего было бы рассмотреть величину r{n,q), т. е. количество помеченных ориентированных графов с п вершинами и без ориентированных циклов, причем из q помеченных вершин этих графов выходит по одной дуге. Следовательно, количество помеченных ориентированных деревьев с указанным корнем равно г(п, п - 1). На основе таких обозначений и за счет простого подсчета аргументов получим, что для любого фиксированного целого числа т

r{n,q) = Y2(Jiy)i~~4~k), еслиО <т <n-q, (18)

r{n,q) = J2{l)Hn-l,q-k), ecлиq = n-l. (19)

Первое из этих соотношений получается, если разбить непомеченные вершины на две группы, А и В, с т вершинами вАип - q - т вершинами в В. Затем q помеченных вершин разобьем на к вершин, с которых начинаются пути, ведущие в А, и q - к вершин, с которых начинаются пути, ведущие в В. Соотношение (19) получается, если рассмотреть ориентированные деревья, в которых корень имеет степень к.

Вид этих соотношений указывает на то, что в данном случае можно было успешно использовать производяшую функцию:

Gm{z) = r(m,0) + r(m + 1, \)z + - " " -fc!~

С помощью соотношения (18) получим Gn-q{z) = Gm{z)Gn-q-m{z) и, СЛСДОВа-

тельно, С помощью метода индукции по m получим Gm{z) = Gi{z). Затем из соотношения (19) получим

i »(", п - 1)2"" г(п - 1, п - 1 - k)z" 1 () = Е-(п-1)! = Е Е-к\{п-1-ку.-

п>1 к>0 п>1

*:>0 *:>0

Иначе говоря, для Gi {z) = w решение этой задачи заключается в поиске коэффициентов решения такого трансцендентного уравнения:

W = е"". (20)

Это уравнение можно было бы решить с помощью формулы обращения Лагранжа следующим образом. Из 2 = С (С) следует, что

=I19i"-\0), (21)

п>1

где ffn(C) = /(С)", 6СЛИ / - аналитическая функция в окрестности нуля и /(0) ф О (см. упр. 4.7-16). В данном случае, предполагая, что С = •zw, f{Q = е, получим

п>0

ЧТО полностью соответствует приведенному выше решению.

Дж. Н. Рейни (G. N. Raney) показал, что этот метод можно применить и для решения уравнения более общего вида

представив w в виде степенного ряда по yi, • • • ,у« и zi,... ,Zs. Для этого общего случая рассмотрим s-мерные векторы целых чисел

П = (П1,П2,...,П«)

и запишем для удобства

Еп = П1 + П2 Н-----f- Hg.

Предположим, что имеется s цветов Ci,С2,..., Cg, и рассмотрим ориентированные графы, каждой вершине которых присвоен определенный цвет, например

(23)

4 Желтый 5>i Красный

Пусть г(п, q)-количество таких способов проведения дуг и присвоения цветов вершинам {1,2,..., п}, что

i) для I < г < S существует в точности щ вершин с цветом Ci (следовательно, п = Еп);

ii) существует q дуг, которые выходят по одной из каждой вершины {1,2,... ,9};

iii) для 1 < г < S существует в точности дуг, проходящих из вершин с цветом С, (следовательно, q = Eq);

iv) не существует ориентированных циклов (следовательно, 9 < п за исключением случая, когда q = п = 0).

Назовем это (n,q)-nocTpoeHHeM.