17. Должен существовать в точности один цикл xi, хг, Хк, где /(xj) = Xj+i и f{xk) = Xl. Перечислим все такие / с циклом длиной к, что итерации каждого х в конце концов будут включаться в этот цикл. Определим каноническое представление /(Vi), /(V2), f{Vm-k) так же, как в данном разделе. f{Vm-k) находится в цикле, поэтому продолжим создание "канонического представления", записывая остальную часть цикла f{f{Vm-k)), /(/(/(Vm-/fc))) и т. д. Например, функция с m = 13 для показанного здесь графа приводит к такому представлению: 3, 1, 8, 8, 1, 12, 12, 2, 3, 4, 5, 1. Получим последовательность т - 1 чисел, в которой последние к чисел будут различными. И наоборот, начиная с такой последовательности, можно выполнить обратное построение (при условии, что известно к). Следовательно, существует в точности m-m"""*" таких функций, содержащих fc-цикл. (Для знакомства с другими аналогичными результатами обратитесь к упр. 3.1-14. Формулу m"~Q(m) впервые получил Л. Кац; он привел ее в работе L. Katz, Annads of Math. Statistics 26 (1955), 512-517.)

18. Для реконструкции дерева на основе последовательности si, s2, Sn-i начнем с si в качестве корня и последовательно будем присоединять дуги, ведущие в si, S2, .... Если вершина Sk ранее встречалась, то оставим начальную вершину дуги, ведущей к Sk-i, без имени, в противном случае присвоим этой вершине

имя Sk. После размещения тг - 1 дуг присвоим имена всем безымянными вершинам с помощью цифр, которые еще не встречались, в порядке возрастания по мере их появления.

Например, на основе представления 3, 1, 4, 1, 5, 9, 2, 6, 5 можно построить дерево, показанное справа. Между этим методом и методом, описанным в данном разделе, не существует никакой простой связи. О других представлениях речь идет в Е. Н. Neville, Proc. Cambridge Phil. Soc. 49 (1953), 381-385.

19. Каноническое представление имеет точно п - к различных величин, поэтому перечислим последовательности тг-1 чисел, которые обладают данным свойством. Таким образом, ответ-тгС::}.

20. Рассмотрим каноническое представление таких деревьев. Тогда возникает вопрос: сколько членов разложения (xi -- • • • -Ь Хп)"~ имеют ко нулевых степеней, ki степеней 1 и т. д. Понятно, что каждое такое число равно коэффициенту такого члена, умноженного на количество таких членов, а именно:

(гг-1)!

(0!)*о(1!)*1 ...(n!)*» ko\ki\...kJ

21. Для четного количества вершин 2т таких деревьев не существует, а для нечетного количества вершин тг = 2т + 1 ответ можно получить на основе упр. 20 с ко = т + 1, к2=т,а именно-(";+)(2т)!/2™.

22. Точно тг"~; действительно, если X - некоторая вершина, то существует взаимно однозначное соответствие между свободными деревьями и ориентированными деревьями с корнем Л.

23. Каждое непомеченное упорядоченное дерево можно пометить п! способами, и все такие помеченные упорядоченные деревья будут различными. Поэтому их общее количество равно 7i!6n-i = (271 - 2)!/(т1 - 1)!.

24. Деревьев с фиксированным одним корнем столько же, сколько деревьев с другим корнем, поэтому ответ будет равен ответу из упр. 23, умноженному на \/п. Например, в данном случае ответ - 30.

25. r{n,q) = (71 - q)n~ для О < g < п. (Особый случай - s = 1 для уравнения (24).)

26. {к = 7)

Красный/4 Синий

елтый 9 «Синий

1 /Красный 2 Желтый

Синий f3 7 «Красный

5 Синий

27. Пусть дана такая функция д с областью определения {1,2,.. ,7-} и областью значений {1,2, что добавление дуг от Vk к Ugk) не приводит к появлению ориентированных циклов. Построим последовательность ai, Ог. Назовем вершину Vk "свободной", если не существует ориентированных путей от к 14 для любых j ф к. Поскольку не существует ориентированных циклов, должна существовать по крайней мере одна свободная вершина. Пусть 6i -наименьшее целое число, для которого вершина 14; является свободной. Предположив, что выбраны числа bi, bt, допустим, что bt+i - наименьшее целое число, отличное от 6i, .. , bt, для которых Ht+i является свободной вершиной в графе, полученном путем удаления дуг от 14 к Ugb) для 1 < к < t Это правило определяет перестановку 6162. -бг целых чисел {1, 2,..., г}. Пусть ак = д{Ьк) для I < к <г, следовательно, определена такая последовательность, что 1 < а*, < g для 1</г<ги1<аг<р.

И наоборот, если дана такая последовательность ai, аг, назовем вершину 14 свободной, если не существует такого j, для которого Uj > р и /(oj) = к. Поскольку Ог < р, имеется не более г - 1 несвободных вершин. Пусть 61 - наименьшее целое, для которого вершина 14; является свободной. Предположив, что выбраны 61, .. ,bt, допустим, что bt+i --наименьшее целое, отличное от 6i, ..., 6t, для которых вершина 14,+1 является свободной по отношению к последовательности at+i, , а,. Данное правило определяет перестановку 6162 ..бг целых чисел {1,2, ...,г}. Пусть д{Ьк) = ад, для 1 < А: < г; это определяет такую функцию, что добавление дуг от 14 к Ugk) не приводит к появлению ориентированных циклов.

28. Пусть / - любая из п"*" функций с областью определения {2,..., т} и областью значений {1,2,... ,7г}. Рассмотрим ориентированный граф с вершинами Ui,... ,Um,Vi,... ,V„ и дугами от Uk к Vfk) для 1 < А: < т. Применим результат упр. 27 с р = 1, q = т, г = 71, чтобы показать, что существует ттг"" способов добавления дополнительных дуг от V к и для получения ориентированного дерева с корнем Ui. Поскольку между рассматриваемым множеством свободных деревьев и множеством ориентированных деревьев

с корнем Ui существует взаимно однозначное соответствие, ответ будет таким: гг" т" [Это построение можно значительно обобщить; см. D. Е. Knuth, Canadian J. Math. 20 (1968), 1077-1086.]

29. Если у = х, то {tz)y = \пу и достаточно доказать тождество для t = 1. Затем, если ZX = \пх, на основании результата упр. 25 получим, что = Yk k{ni,l)z для неотрицательных целых чисел т. Следовательно,

== Е = Е = Е i П>-

k j,k к J

к > к

[В упр. 4.7-22 приводится значительно более общий результат.]

30. Каждый описанный граф определяет множество Сх С {l,...,n}, где j принадлежит Сх тогда и только тогда, когда существует путь от tj к г, для некоторого i < х. Для данного множества Сх каждый описанный граф состоит из двух независимых частей: одна часть принадлежит множеству х{х + t\z\ 4- • • • -Ь tnZnY +en-i ррафов с вершинами

г,, Sjfc, tj для г < X и j е Сх, где tj = [j е Сх], а другая - множеству у(у -Ь (1 - ei)«i -I----

+ (I ~ en)Zn) графов с остальными вершинами.

31. G{z) = Z + G{zf + Gjzf + G{zy + = z + G(z)7(l - Giz)). Следовательно, Giz) = \{1 + z - Vl - 6г + z2 ) = z + z + 3z + Uz + 45z + [Замечания. Другая задача, эквивалентная данной, была поставлена и решена Ф. В. К. Э. Шредером [F. W. К. Е Schroder, Zeitschrift Кг Mathematik und Physik 15 (1870), 361-376], который определил количество способов вставки неперекрывающихся диагоналей в выпуклом (тг + 1)-угольнике. Эти числа для тг > 1 всего вдвое меньше чисел, полученных в упр. 2.2.1-11, так как согласно грамматике Пратта в гюсоциированном дереве допускается наличие корня со степенью 1. Асимптотическое значение вычисляется в упр. 2.2 1-12. Любопытно, что значение [z"] G(z) = 103049, похоже, было найдено еще Гиппархом во 2 веке до н. э. как количество "утвердительных сложных суждений, которые можно вывести на основании только десяти простых суждений"; см. R. Р. Stanley, АММ 104 (1997), 344-350.]

32. Ни одного, если по / 1 -Ь пг -h 2пз + Зп4 + (см. упр. 2.3-21). В противном случае

(по -bni -I-----hnm - l)!/no!ni!...nm!.

Для доказательства этого результата напомним, что непомеченное дерево с п = по -Ь п1 -!-••+ Пт узлами характеризуется последовательностью did2 .. .dn степеней узлов в обратном порядке обхода (раздел 2.3.3). Более того, данная последовательность степеней соответствует дереву тогда и только тогда, когда E*=i(l ~ dj) > О для О < < п. (Это важное свойство польской системы обозначений (или польской нотации) легко доказывается с помощью метода индукции; см. алгоритм 2.3.3F с функцией построения дерева /, которая подобна функции TREE из раздела 2.3.2.) В частности, di должно быть равно 0. Следовательно, ответом для этой задачи будет количество последовательностей 2 .. .d„, в которых щ раз встречается j для j > О, а именно - полиномиальный коэффициент

\По - 1, п1, . . . , Пт )

минус количество таких последовательностей di ...dn, для которых Ej=2(-- ~ з) < О определенного fc > 2.

Эти последовательности можно перечислить следующим образом. Пусть t - такое минимальное значение, что Ej=2(l ~ з) < О- Тогда 5Zj=2(l " j) ~ 1 < s < dt.