и можно построить подпоследовательность d2. .d = dt-i • • • dQdt+i dn, в которой щ раз встречается j для j ф dt, - \ раз встречается j для j = dt- Тогда idj=2( ~ j) равна dt для к = п и эта сумма равна dt - s для к = t. Для < t получим

2<j<t 2<j<t-k 2<j<t

Отсюда следует, что для данного s и любой последовательности d2 ... dn это построение можно обратить. Значит, количество последовательностей di -. - dn для заданных значений dt и S можно выразить с помощью полиномиального коэффициента

f )•

\По, - - - , Tldi - 1, ... , Пт I

Тогда количество последовательностей di- - - dn, которые соответствуют деревьям, можно получить за счет суммирования всех допустимых значений dt и s:

причем последняя сумма равна 1.

Еще более простое доказательство этого результата предложено Дж. Н. Рэйни (G. N. Raney) [см. TVansactions of the American Math. Society 94 (1960), 441-451]. Если dl di - . .dn - произвольная последовательность, в которой щ раз встречается j, то существует в точности одна циклическая перестановка d/t... dndi ... dk-i, которая соответствует дереву, а именно: перестановка, в которой fc - такое максимальное значение, что сумма Ej-i (1 - dj) является минимальной. [По-видимому, этот результат для бинарных деревьев впервые был получен Ч. С. С. Пирсом (С. S. S. Peirce) в неопубликованной рукописи; см. его книгу New Elements of Mathematics 4 (The Hague: Mouton, 1976), 303-304. Для i-арных деревьев доказательство предложено Дворецким и Моцкиным; см. Duke Math. J. 14 (1947), 305-313.]

Еще одно доказательство предложено Дж. М. Бергманом (G. М. Bergman), в котором согласно методу индукции dkdk+i заменяется на {dk + dk+i - 1), если d*, > О [Algebra Universalis 8 (1978), 129-130].

Описанные выше методы можно обобщить и показать, что количество упорядоченных и непомеченных лесов с / деревьями и щ узлами степени j равно (п - 1)! по! ml... Пт!, если выполняется условие по = / -Ь П2 -Ь 2пз

33. Рассмотрим количество деревьев с ni узлами, которые помечены номером 1, с П2 узлами, которые помечены номером 2, и т. д., таких, что каждый узел с меткой (номером) j имеет степень Cj. Пусть это число равно с(п1,П2,...) с фиксированными степенями Ci,

Ci, ---- Производящая функция G{zi, Zi,...) = c(ni, пг,... )г"г2 ... удовлетворяет

тождеству G - ziG Н-----hZrG, так как ZjC перечисляет деревья с корнями, помеченными номером j. Согласно результату предыдущего упражнения

rtr, г, ({П1+П2 + ----1У. если(1-еОп1 + (1-е2)п2 + --- = 1;

С(П1,П2,...) = < ni!n2!...

[о в остальных случаях.

Вообще говоря, поскольку G перечисляет все упорядоченные леса с такими ярлыками, для целых / > О получим

у (П1+П2 + ----1)!/ п,

ni!n2!...

/=(1-е1)п1+(1-е2)п2Ч-

Эти формулы имеют смысл, когда г = оо, и, по существу, они эквивалентны формуле обратного преобразования Лагранжа.

РАЗДЕЛ 2.3.4.5

1. Всего существует () таких деревьев, поскольку узлы с номерами 8-12 можно присоединить в любом из 8 мест под узлами 4-7.

3. Согласно методу индукции по т данное условие является необходимым. И наоборот, если EJLi 2"- = 1, нужно построить расширенное бинарное дерево с длинами пути h, , lm- Если т - 1, имеем /i = О, и построение становится тривиальным. В противном случае можно предположить, что / упорядочены так, что h = h = = Iq > Iq+i > lq+2 > > lm > 0 для некоторого g с 1 < g < m. Тогда 2i~ = Ejli 2~~ = Й + 4-° число. Следовательно q - четно. На основании метода индукции по т можно доказать, что существует дерево с длинами пути h - 1, /з, U, , 1т- В таком дереве заменим один из внешних узлов на уровне /: - 1 внутренним узлом, дети которого находятся на уровне /1 = h.

4. Сначала построим дерево по методу Хаффмэна. Если Wj < Wj+i, то Ij > Ij+i, так как это дерево является оптимальным. Построение из ответа к упр. 3 теперь позволяет получить другое дерево с теми же длинами пути и весами в соответствующей последовательности. Например, дерево (11) принимает вид

[См. САСМ 7 (1964), 166-169.]

5. (а) Ьпр = bkrbia. Следовательно, zB(ii), liJz) = B(ii), z) - 1.

k+l=n-l r+s+n-l=p

(b) Возьмем частную производную по w.

2zB{w, wz)(Bw{w, wz) + zBz{ui, wz)) = Bwiui, z).

Значит, если H{z) = B„(l,z) = Епо", найдем H{z) = 2zB{z){H{z) + zB{z)). Из известной формулы для B{z)

H{z)

3n + l /271 n +

r(„)-

Среднее значение равно hn/bn-

(с) Асимптотически это выражение равно п\ркп - Зтг -Ь 0{у/п).

[См. решения аналогичных задач в работах John Riordan, IBM J. Res. and Devel. 4 (1960), 473-478; A. Renyi and G. Szekeres, J. Austraiian Math. Soc. 7 (1967), 497-507; John Riordan and N. J. A. Sloane, J. Austraiian Math. Soc. 10 (1969), 278-282; a также в упр. 2.3.1-11.]

6. n -Ь s - 1 = tn.

7. E = (t-l)/--tn.

8. Суммируя no частям, получим ZJJi Logt(( ~ 1))J = Щ ~ Yl: "Д суммировгшие справа выполняется по таким к, что 0<А;<пи(* - l)A:-bl = t- для некоторого j. Последнюю сумму можно представить в виде 5Zj=i( ~ !)/(* ~

9. Воспользуйтесь методом индукции по размеру дерева.

10. Добавив (если это необходимо) дополнительные нулевые веса, можно предположить, что mmod (t - 1) = 1. Чтобы получить t-арное дерево с минимальной взвешенной длиной пути, на каждом этапе объединим наименьшие значения t и заменим их суммой этих же значений. Доказательство в таком случае выполняется, как для бинар1юго дерева. Искомое тернарное дерево показано справа.

Ф. К. Хван (F. К. Hwang) заметил [SIAM J. Appl. Math. 37 (1979), 124-127], что аналогичная процедура справедлива для построения деревьев с минимальным взвешенным путем, имеющих произвольно заданное мультимножество Степеней. Для этого следует объединить t весов на каждом этапе, где t является минимально возможным.

11. Десятичная система обозначений Дьюи является двоичным представлением номеров узлов.

12. Согласно результату упр. 9 средний размер поддерева с корнем в этом узле равен внутренней длине пути, делешюй на п плюс 1. (Этот результат верен как для деревьев общего типа, так и для бинарных деревьев.)

13. [См. J. van Leemven, Proc. 3rd Internationa] CoUoq. .Automata, Languages and Programming (Edinburgh University Press, 1976), 382-410.]

HI. [Инициализация.] Установить A[m -1 + i] i- w, для 1 < i < m. Затем установить A[2m] <-(X>, xi-m, ii-m + 1, ji-m-1, km. (B данном алгоритме A[i] < < A[2m - 1] -очередь неиспользованных внешних весов; А[к] > > A[j] - очередь неиспользованных внутренних весов, которая пуста в случае, когда j < к; X и У - текущие левый и правый указатели.)

Н2. [Поиск правого указателя.] Если j < к или АЩ < A[j], то установить у i и г 4- г -Ь 1; в противно.м случае установить yi-jajj - 1.