Например, если Ci-красный цвет, Сг-желтый цвет и Сз-голубой цвет, то (23) схематично представлйет ((3,2,2), (1,2,2))-построение. При наличии только одного цвета получим уже решенную задачу для ориентированного дерева. Идея Рейни заключалась в обобщении одномерного построения до s размерностей.

Пусть п и q -фиксированные s-мерные векторы неотрицательных целых чисел, а п = 5Zn, q = 5Zq. Для каждого (п,я)-построения и каждого числа к, 1 < к < п, определим каноническое представление, которое состоит из следующих четырех компонентов:

a) числа t, q < t < п;

b) последовательности n цветов, в которой присутствует П{ цветов С,;

c) последовательности q цветов, в которой присутствует qt цветов Cj;

d) последовательности qi элементов множества {1,2,..., п,} для 1 < г < s.

Это каноническое представление определяется следующим образом. Сначала перечислим вершины {1,2,... ,q} в порядке Vi,V2,. ,Vg канонического представления ориентированных деревьев (как определено выше), а затем запишем под вершиной Vj номер вершины f(Vj) на дуге, проходящей от Vj. Пусть t - f{Vg), а последовательность цветов (с) соответствует цветам вершин f{Vi),...,f{Vg). Пусть последовательность цветов (Ь) соответствует цветам вершин к,к + 1,... ,п,1,... ,к - 1. Наконец, пусть г-я последовательность (d) равна хц,Х{2,.. Хщ., где xij = т, если j-й элемент цвета Cj последовательности /(Vi),...,/(F,) является т-и элементом цвета d последовательности к, к + \, ..., п, I, ..., к - I.

Например, рассмотрим графы (23) и допустим, что fc = 3. Начнем с перечисления вершин Vi,...,Vb и /(Fl),..., /(f5) и номеров под ними:

1 2 4 5 3 7 6 3 3 6

Значит, i = 6, а последовательность (с) представляет соответственно цвета вершин 7, 6, 3, 3, 6, а именно - красный, желтый, синий, синий, желтый. Последовательность (Ь) представляет соответственно цвета вершин 3, 4, 5, 6, 7, 1, 2, а именно - синий, желтый, красный, желтый, красный, синий, красный. Наконец, чтобы получить элементы такого цвета, нужно составить следующую таблицу.

Элементы Элементы Шифрование

Цвет такого цвета среди такого цвета среди столбца 3

3,4,5,6,7,1,2 7,6,3,3,6 с помощью столбца 2

Красный 5,7,2 7 2

Желтый 4,6 6,6 2,2

Синий 3,1 3,3 1,1

Итак, искомыми последовательностями типа (d) будут 2; 2,2 и 1,1.

На основе такого канонического представления можно восстановить исходное (п,я)-построение и число к, поступив следующим образом. Исходя из (а) и (с) узнаем цвет вершины t. Последний элемент последовательности (d) с таким цветом в сочетании с (Ь) позволяет узнать расположение числа t в последовательности fc,..., п, 1,..., fc - 1. Таким образом, узнаем значения fc и цветов всех вершин. Тогда последовательности (d) вместе с (Ь) и (с) определят /(Vi),/(V2),...,/(F)

и наконец ориентированный граф будет полностью восстановлен после определения расположения Vi,...,Vq так, как это было сделано для ориентированных деревьев.

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

( " )

вариантов для (Ь),

.91, •••,9*

вариантов для (с) и п п... п вариантов для (d), которые выражены в виде полиномиальных коэффициентов. Общий результат найдем, разделив произведение полученных величин на п:

Кроме того, можно получить аналогичные (18) и (19) соотношения:

r(n,q)= V fV(t,k)r(n-t,q-k), еслиО<т<Е(п-я), (25) k,t

E(t-k)=m

при условии, что г(0,0) = 1 и г(п, q) = О, если значение щ или qi отрицательно либо если q > п;

г(п,q) = Е Е () - ч - ««) " Еп = 1 + Eq, (26)

где Cj - вектор с единицей в позиции i и нулями в остальных позициях. Соотношение (25) основано на разбиении вершин {q + 1,... ,п} на, две части стип - q - тп элементами в каждой. Второе соотношение получается за счет удаления единственного корня и рассмотрения оставшейся после этого структуры. Рассмотрим теперь следующий результат.

Теорема R (George N. Raney, Canadian J. Math. 16 (1964), 755-762). Пусть

гЫ, q) m

E 7?2/Г---2/Г-Г---1% (27)

l:(n-q)=l

где r(n, q) определяется формулой (24), a n, q -s-мерные целочисленные векторы. Тогда w удовлетворяет тождеству

w=yie + У2е + --- + yse. (28)

Доказательство. С помощью (25) и метода индукции по m получим, что

"" Е "-уТ---у4---4- (29)

E(n-q) = m

Затем по формуле (26) находим, что

г(п-еь q-fcee) „г „п,

E(n-q) = l

(n,q) „.ni

E(n-q)=fc

i=i *

в приложениях особенно большое значение имеет специальный случай, когда s = 1h2i = 1b (27) и (28), а потому следующее выражение получило название "функция дерева" (tree function):

itV S (Eq-fc)! •••

п>1

ПУ) = Т.У"=уе1 (30)

Некоторые замечательные свойства этой функции приведены в работе Корлеса, Гонне, Харе, Джефри, и Кнута [Advances in ComputationaJ Math. 5 (1996), 329-359].

Обзор формул перечисления деревьев, основанных на умелом применении производящих функций, предложен И. Дж. Гудом (I. J. Good) [Proc. Cambridge Philos. Soc. 61 (1965), 499-517; 64 (1968), 489]. Разработанная совсем недавно Андре Джойалем (Andre Joyal) математическая теория видов {theory of species) [Advances in Math. 42 (1981), 1-82] позволила расширить эту проблему до более высокого уровня, на котором алгебраические операции над производящими функциями непосредственно соответствуют комбинаторным свойствам структур. Многочисленные примеры из этой прекрасной и поучительной теории вместе с обобщениями многих полученных выше формул можно найти в к1шге F. Bergeron, G. Labelle, and P. Ler-oux, Combinatorial Species and Tree-like Structures, (Cambridge Univ. Press, 1998).

УПРАЖНЕНИЯ

1. [M20] (Задача Д. Пойа (G. Polya).) Покажите, что

A(z) = г • exp {A{z) + i(г) + А(г) + •••)

[Указание. Возьмите логарифм выражения (3).]

2. [НМ24] (Задача Р. Оттера (R. Otter).) Покажите, что числа а„ удовлетворяют такому соотношению:

non+i = aiSni + 2a2Sn2 Н-----1- na„Snn,

Snk = E Un+l-jk-l<j<n/k

(Эти формулы очень полезны для вычисления Оп, так как Snk = S(n-k)k + an+i-/t)