и пусть V{z) = Vn+ Vn+iz------h Vin-iz" удовлетворяет уравнению

V{z + zUiz)) = (1 + z-w(z))V{z) + z-Siz) + 0{z-+).

С помощью второго алгоритма решаем W{z)U{z) + zU{z) = V{z) + 0(г") для U{z) = Uo + Uiz + • • + Un-iz"~, где V{z), W{z) и n заданы. Если n = 1, то положим Uo = V{0)/W{0) или выберем Uo произвольно для случая, когда V{0) = W{0) = 0. Перейдем от п к 2п. Пусть W{z)U{z) + zU{z) = V{z) - zR{z) + Oiz"") и пусть U{z) = Un + + U2n-iz"- -решение уравнения (n + Wiz))U{z) + zU{z) = R{z) + 0(г").

Применив обозначения (27), первый алгоритм можно использовать для решения уравнения V{U(z)) = U{z){zlU{z)YV{z) с любой требуемой точностью. Положим V{z) = zV{z). Чтобы найти P(z), предположим, что V{P{z)) = Р(г)К(г) + 0(2*"+"). Данное уравнение справедливо для п = 1, когда P{z) = z + az и а - произвольное. Можно перейти от п к 2п, полагая, что V{P{z)) = P(z)F(z)+z*"+"il(2)+0(2*~+"), и заменяя P{z) на P(z)+z"P{z), где второй алгоритм используется для нахождения полинома P{z), такого, что {к + п- zV{Piz))/Viz))P{z) + zP{z) = (zIV{z))R{z) + 0(г").

15. Из дифференциального уравнения U(z)/U{z) = следует, что (7(г)~* = 4-с для некоторой постоянной с. Таким образом, находим, что {/"(г) = z/(l 4-спг~*)*°~.

Аналогично решаем (27) для произвольного V{z): если W{z) = 1/V{z), то W{U\z)) = W{z) + пс для некоторого с.

16. Нужнопоказать,что[«"]«"+Ч(п + 1)Д!ь+1(0/У(<)"-"Ли<)/У(<)"") =0. Это следует из равенства (n4-l)fiifc+i(0/y(0"-n!fc(0/y(0" = №(<)/У(0")- Поэтому получаем

n-Mt"-i]i(0<"/vW" = (п-1)-М<"-2]Д2(<)<"-уу(0"- = •• = l~4t]K{t)t/V{t) =

[t]Rn{tyVi=Wn.

17. Соберем коэффициенты при ху". Из формулы свертки следует, что (t,")n(/+m) = Ек (2)t*iW(„-*)m, аэто эквивалентно равенству [г"] У(2)+"=Е*([г*]У(г))([г""-*] У(г)"), являющемуся частным случаем (2).

Замечание. Название "степеноид" введено Й. Ф. Стеффенсеном (J. F. StefFensen), который первым из многих авторов изучил удивительные свойства этих патиномов [Acta Mathematica 73 (1941), 333-366]. Обзор литературы и дальнейшее обсуждение предмета можно найти в следующих нескольких упражнениях, а также в статье D. Е. Knuth, The Mathematica Journal 2 (1992), 67-78. Одним из результатов, патученных в этой статье, является асимптотическая формула Vn{x) = e*()"(l - Vty + 0{у) + 0{х~)), если Vl = 1, и sV(s) = у и у = п/х ограничены, когда х оо и п -> оо.

18. Имеем У„(х) = Zk ["] Viz/kl = п\ [г"] el Поэтому

V„ix)/x ={п- 1)! [z"-i] V{z) е\

когда п > 0. Равенство можно получить, если приравнять коэффициенты при г"" в равенстве V{z)e+ = Viz)eeK

19. Согласно полиномиальной теореме 1.2.6-(42) имеем -.1

•""• = ["41!"+2!" +••]

Ln! fVlYWV2\ (Vn\>

ki\k2\...kn\\V.) \2\) -Лп\)

*l+*2-t-----l-*n=m

*1+2*2H-----t-n*„=n

ki,k2.....*„>0

Эти коэффициенты появляются также в формуле Арбогаста (упр. 1.2.5-21). Эти члены уравнения можно привести в соответствие с множеством разбиений, как объясняется в

ответе к данному упражнению. Рекуррентная формула

позволяет вычислить столбец к по столбцам 1 и А: - 1; она легко интерпретируется в терминах разбиений {1,..., п}, поскольку существует ("Zj) способов включения элемента п в подмножество размера j. Несколько первых строк матрицы имеют следующий вид.

t;3 3viV2 Vl

V4 4«1«3+3«2 6ViV2 Vl

Vs 5WlW4 + 10«2«3 ISwiwi + 10WlW3 10ViV2 Vl

20. [z]W{z) = Zj{[z]U{z)){[z"]Vizy), следовательно, Wnk = {n\/k\)j:.iik\/j\)ujk) x {{j\/n\)vnj). [E. Jabotinsky, Comptes Rendus Acad. Sci. Paris 224 (1947), 323-324.]

21. (a) Если Uiz) = aW{/3z), получим = fj [z"] (аИ(/3(г))* = al3"-Wnk; в частности, если (7(г) = У"Ч(г) = -VF(-2), тоип* = (-l)"~°tonik;. Значит, согласно упр. 20 Е* UnkVkm и Eik; inifcUfc.n соответствуют функции г.

(Ь) [Решение И. Гессель (Ira Gessel).] Данное тождество фактически эквивалентно формуле обращения Лагранжа: имеем Wnk = (-l)~«tifc = (-l)""* fr [2"] У"(г)°, и согласно упр. 16 коэффициент при г" в V~{zУ равен п" [<""] А:+°~7У()"- С другой стороны, определим V(-k)(-n)- Это (-А:)[г"] (V(z)/z))"", в свою очередь, равно ( l)n-fc(„ 1)... (А: + l)ifc [г-] 2"+*-7К(г)".

22. (а) Если У(г) = (7<°>(г) и 1У(г) = У<>(г), то

И/(г) = У(г1У(г)) = U{zW{z) У(гИ/(г))°) = (7(г1У(г)°+).

(Отметим разницу между данным законом и подобными формулами UWz) - U{z), UMW(z) = t/[°l(z), которые применяются в итерации.)

(b) Bz) - производящая функция для бинарных деревьев, 2.3.4.4-(12), равная W{z)/z, в примере z = t - t, который следует за алгоритмом L. Кроме того, Bz) - производящая функция для <-ичных деревьев (упр. 2.3.4.4-11).

(c) Указание эквивалентно равенству zU°z)° = W~\z), которое, в свою очередь, эквивалентно формуле гС/°*(г)"/(7(г(7°*(2)")" = z. Из теоремы обращения Лагранжа (упр. 8) следует, что [2"] 1У!-Ч(г) = [г"] 1У(г)~", где х - положительное целое число. (Здесь W{z)~, ряд Лорана, степенной ряд, деленный на степень z; можно воспользоваться обозначениями [г™] У(г) для ряда Лорана, как и для степенного ряда.) Следовательно, [г"]С/<°>(г)" = [z]{W-\z)/z)= [2"+"/"] 11-4(2)"/° равняется

4 [2-/"] 1У(2) -= [2-/"] 2-/«t/(2)+"°,

где х/а - положительное целое число. Мы получили результат для бесконечного множества а. Этого достаточно, так как коэффициенты U"{z) - полиномы от а.

Выще уже рассматривались частные случаи данного результата (в упр. 1.2.6-25 и 2.3.4.4-29). Одно запоминающееся следствие указания - это случай, когда а = -1:

W{z) = zU{z) тогда и только тогда, когда W\z) - z/U~{z).

(d) Если i7o = 1 и Vn(x) - степеноид для V{z) = lnU{z), то, как уже было доказано, xVn{x+na)/{x+na) -степеноид для In t/°*(2). Значит, можно вставить данный степеноид в первое тождество, заменяя у на у - an во второй формуле.

23. (а) Имеем U = I + Т, где Т" равно нулю в строках < п. Значит, In С/ = Г - + ----обладает таким свойством exp(alnDO = / + {°)Т + (°)Г Н----= 11". Каждое

вводимое и°-это полином от а, и соотношения упр. 19 выполняются всякий раз, когда Q-положительное целее число; кроме того, (7"-степенная матрица для всех а и ее первые столбцы определяют {/"(г). (В частности, -степенная матрица; это другой метод обращения U{z).)

(b) Так как U" = I + elnU + О(б), получим

Ink = Иий = 2: [г"][б] (z + еЦг) + 0(б=))= = g [z"] kz-Liz).

(c) UHz) = [б] C/f"+5(2), и получаем

i7["+l(2) = i7"i(i7k)) = + 6L(2) + 0(б)).

Также г7["+1(г) = U\U\z)) = U"\z) + eL{U\z)) + 0{е).

(d) Равенство следует из того факта, что U меняются местами с In U. Оно определяет 1п-1, когда п > 4, потому что коэффициент при в левой части равенства равен nu2, а коэффициент в правой части равенства есть Wn(n-i) = (2)"2- Аналогично, если иг = • = Uk-i = О и / О, получаем /а- = иа, и по рекуррентной формуле для п > 2к определяем 1к+1, 1к+2, Левая часть равенства имеет вид + Jz„+i s,ua 4- • •, а правая - In + {l)ln+i-kUk 4- Вообще, h = u2, I3 = из - fua, h = u4 - бигиз + u2, 5 = U5 - u2u4 - 5U3 4- ulu3 - 20U2.

(e) Справедливо U = Ет()"7п*!> и для фиксированного m вклад в Un = u„i от m-ro члена равен Ептп„, 1 • ./пгтцпщо, где суммирование по п = > • • > ni > По = 1. Применим полученный результат к п. (Ь). [См. IVans. Amer. Math. Soc. 108 (1963). 457-477.]

24. (a) Из (21) и упр. 20 получаем U = VDV~, где V - степенная матрица функции Шредера и D - диагональная .матрица diag(u, и, и,...). Тогда можно взять

\nU = Kdiag(lnu,21nu,31nu,...)K-\

(b) Равенство WYDV = VDV-W влечет равенство {V-WV)D = D(V-WV). Диа-гонсшьные элементы матрицы D различны, значит, VTW должна быть диагональной матрицей D. Таким образом, W = VDV~ и W имеет такую же функцию Шредера, как и и. Следовательно, О и = УО-у-, где а = (In И1)/(1п i7i).

25. Должно быть к = I, потому что [г*+~] С/(К(г)) = Uk+i~i + Vk+i-i + kUkVi. Для полного доказательства достаточно показать, что Uk = Vk я U{V{z)) = V{U{z)) влечет U{z) = V{z). Предположим, что / минимально с Ui ф Ц, и пусть п = к + I - 1, Тогда получаем и„к - v„k = (7)(и( -vi), Unj = Vnj для j > к, Uni = (")"it и Unj = О для I < j < п. Сейчас сумма EjMijj = 4- UnkVk 4- • 4- Univi +Vn должна равняться Zj VnjUj- Значит, (")(и/ - vi)vk = il)vk{ui - Vl), HO {l) = тогда и только тогда, когда к = 1.

[Из данного и предыдущего упражнений можно предположить, что U{V(z)) = V{U(г)) только тогда, когда одно из С/ и V является итерацией другого. Но это необязательно, если Ul и Vl -корни из единицы. Например, если Vi = -1 и U(z) = V\z), V не является итерацией С/ и С/-итерацией V.]

26. Записав U{z) = U[o]{z) 4- zUiz), получаем U{V{z)) = C/[o](Vi2 + Кг" + ) 4-

V{z)Um{Viz 4- Viz" H----) (no модулю 2). Время счета удовлетворяет равенству T{N) =

2T{N/2)+C{N), где C{N) -это, по существу, время, расходуемое на умножение полиномов по модулю z. Можно сделать C{N) = 0(У"") методом, упр. 4.6.4-59 (см. также ответ к упр. 4.6-5).