AOP_Tom2 (1021737), страница 226
Текст из файла (страница 226)
Кроме того, Вбй(«) .— производящая функция для Ьичных деревьев (упр. 2.3.4.4-11). (с) Указание эквивалентно равенству «С! 1(«) = Иб '1(«), которое, в свою очередь, эквивалентно формуле «В1а1(«) /(/(«С1~~(«) ) = «. Из теоремы обращения Лагранжа (упр. В) следует, что [«"] И'!-'1(«)* = а[«] И'(«) ", где х — положительное целое чисто.
(Здесь И'(«) ", ряд Лорана, степенной ряд, деленный на степень «, можно воспользоваться обозначениями [«] !г(«) для ряда Лорана, как и для степенного ряда.) Следовательно, [«" ] Н! 1(«) = [« "] (И"' !(«)/«)'~ = [«"+*~ ] !у ! !(х)*~ равняется 23. [а) Имеем 17 = 1+ Т, где Т" равно нулю в строках ( и. Значит, 1пУ = Т вЂ” -'Т + -'Т вЂ” обладает таким свойством ехр[п!п0) = 1+ (,)Т Ч- (2)Т + = У .
Каждое вводимое [/ - — зто пагИНОм От а, И СОотНОШЕния упр. 19 выполняются всякий раз, когда а — положительное цел/,е число; кроме того, [1 — степенная матрица для всех а и ее первые столбцы определяют 11! (2). (В частности, 5/ ' --степенная матрица; это другой метод обращения 0[2).) [Ь) Так как бн = 1+ е!и 0+ 0(г~), получим и! г 1„» — — [4]и„", = —, [2"][е] (2+ »Ц2) -1- 0(4 )) = — [г"/ 52 'Цг).
(с) е 0! (2) = [4] 0!"+'(2), и получаем У ( ) = [/ ([/ !(2)) = 0 1(2 + 41 (г) + 014 )). Также бб э" (2) = (116(11!»О(2)) = [7! '(2) + 41.(11!ь!(2)) -1-0(ег). (11) Равенство гледует нз того факта, что 0 меняются местами с 1п [/. Оно определяет 1„1, когда и > 4, потому что коэффициент прн 1„1 в левой части равенства равен пкг, а коэффициент в правой части равенства есть и„/„п — — (*')иг. Аналогично, если иг = . и» 1 -- О и щ. у- О, получаем 1» = и» и по рскуррептной формуле для и > 25 определяем 1»ь», 1»чг, ... Левая часть равенства имеет вид 1„-1- („"1)1„41»и» + ., а правая— 1„-Ь (")1,ч/ »1»» + ... Вообще, 12 = пг, 12 = пг — -'пг, 14 = и4 — 5игиг + ги~г, В 11 2 1Я» 2 4 нг — — "пги4 — 5пг + — 'игиг — 20пг.
2 4 (е) Справедливо 11 = 2 „,(!и 11)"'1п»1, и для фиксированного /и вклад в иь = иш от т-го члена равен 2 1,,...1,.„„1„„„, где сумл»ирование по п = п, » п/ > пе = ! Применим полученный резулщат к и. (Ь). [См. Тгапз. А/пег. 51ас11 Вес. 106 (1963). 457-477.] 24. (а) Из (21) и упр 26 получаем 11 = Ъ/ВЪ' ', где à — степенная матрица функции Шредера и Р.—.диагональная матрица с(!ай(и, и, и,... ). Тогда можно взять г !и У = !/ейай(1п и, 21пи, 3!ив,... )Г (Ь) Равенство ЪЪ'ЪРЪ' ' = Ъ/В\' 'И' влечет равенство (!' 'И'Г)Р = Р(1' 'И'Г). Диагональные элементы матрицы Р различны, значит, Г '1Ъ'Ъ" должна быть днагоню»ьной матрицей Р'. Таким образом, И' = ГР'Г ' и !Г имеет такую же функцию Шредера, как и 0.
Следовательно, И'1 Ф О и И' = Ъ'Р Г 1, где и = (!и И'1) 1(!и Ус ). 25. Должно быть 12 = 1, потому что [2"э' ']11(Г(2)) = Р»4/ 1-'г !»т/-1 + 511»Г/. Для полного доказательства достаточно показать, что 11» = !'» и Ц!/(2)) = Г([7(г)) влечет 1/(2) =- Г(2). Предположим, что 1 минимально с 01 —,С И. и пусть и = Ь + 1 — 1. Тогда получаем и„» — е„» = (,»)(п1 — с/), и„= ш,/ для 1 > й, и„/ = ( ) и» и и„= О для 1 < 7 ( и.
Сейчас сумма 2 1/ /и/ = и,. +и„».е»+ +и,1о/+я„должна равняться 2»„/и . Значит, / //. (",)(и/ — с/)е» = ("»)е»(и1 — щ), но ( Я, ') = ( ~, ) тогда и только тогда, когда 14 =1. [Из данного и предыдущего упражнений можно предположить, что [1(Г(2) ) = Ъ (0(г) ) только тогда, когда одно из 0 н Г является итерацией другого. Но зто необязательно, если (71 и !/1 — корни из единицы Например, ешш Г» = — ! и [7(2) = Гс~ (2), !' не является итерацией [11/1 и В! /й -итерацией !'.] 26. Записав 0(2) = [1//(2~) + 2У11!(2~), полУчаем 0(Ъ'(г)) = 0!е!(Г/22 .1- Ъг 4 -с- . ) + !/(2)11! 1(Г/гг+ 1224 + ) [по модулю 2) Время счета удовлетворяет равенству Т(Л') = 2Т(Л/12)+С(Л/), где С(Х) — зто, по существу, время, расходуемое на умножение полиномов по модулю гл. Можно»делать С(Х) = 0(Л" ') методом, упр.
4.б.4-59 (см. также ответ к упр. 4.6-5). Аналогичный метод работает по модулю р за время О(рог ы). [Р. Л. Вегпеее!и, в печати.[ 27. Из (И'(йе) — И'(х))1~'(г) = И'(е)(И(9 е) — И(х)) получаем рекуррентную формулу И'э = )' 'ь' ~ ИьИг -ь(7 — 9" ~)/(7" — 1).
[Х ПЯегепсе Ейе. апс( Арр!1се. 1 (1995), 57-60.] 28. Вначале заметим, что д(Цх)И(х)) = (е11(х)) И(х) + (У(х)(бр(х)), так как Г(тп) = 1(т) + 1(п). Кроме того, иидукцией по п получаем б(И(х)") = пЪ~(х)" '51~(с) для всех и > 0 Это равенство необходимо, чтобы показатгч что бе~И~ = ~ >об(г'(с)"/и!) = е ~ 1бр(е). Заменив в данном равенстве г (е) на 1и 17(е), получаем И(х) 61п%~(х) = Ще), поэтому Б(И(е) ) = бе мт01 = е ми~*об(а1пИ(х)) = пр(т) ~ для всех комплексных чисел сс Следовательно, требуемое рекуррентное соотношение имеет вид (а) и', = 1, и'„= 1 е>,((п+ 1)1(4)/с(п) — 1)1геиг„~е; (Ь) Иа =1, И; = Я„„,>,(1(4)/1(п))Ъ~дИ'.~а; ( ) И; =0, И'„=1„+~ „„~,(е(Ы)/1( ) — 1)ИИ'„г [См.
Н. %. Соп!с1, АММ 81 (1974), 9-14. Данная формула справедлива, когда 1 — любая функция, такая, что 1(т) + с(п) = Г(птп) и 1(п) = 0 тогда и только тогда, когда и = 1. но в предположении, что 1 не раскладывается на простые множители, Этот метод можно применять и для степенных рядов с произвольным множеством переменных. Тогда 1— общая степень члена ряда.) Таблица е ВЕЛИЧИНЫ, ЧАСТО ИСПОЛЬЗУЕМЫЕ В СТАНДАРТНЫХ ПОДПРОГРАММАХ И ПРИ АНАЛИЗЕ КОМПЬЮ'ГЕРНЫХ ПРОГРАММ (45 ВОСЬМЕРИЧНЫХ ЗНАКОВ) Величины, располал4енные слева от знака "=", заданы в десятичной системе счисления т е !ил ф ет !4 сзп 1 соа 1 — ('(2) ~(3) 1пф 1/!и ф — 1п1п2 0.1 = 0,01 = 0.001 = 0.0001 = 0.00001 = 0.000001 = 0.0000001 = 0.00000001 = 0.000000001 = 0.0000000001 = ч/2 = /3 = УБ= т/1О = ~/2 = '/3 = Я= !п2 = 1пз = 1п10 = 1/!п 2 = 1/1п 10 = л= 1' = л/130 = 1/л = л т/л = Г(1/2) = Г(1/3) = Г(г/3) = е= 1/е = 0.06ЯЦ БЯЦБ ЯЦ63 Ц631 46Я14 бЗЦб 31463 Ц631 46И5— 0.00507 53412 17270 24365 60507 534!2 17270 24365 60510- 0.00040 61115 64570 65176 76355 44264 16254 02030 Ц672+ 0.00003 21556 13530 704Ц 54512 75170 Э3021 15002 Я5223— 0.00000 24761 32610 70664 3604 ! 06077 17401 56063 Я4417— 0.00000 02061 57Я64 05536 66151 5532Я 07ЦБ 4Ц70 26033+ 0.00000 00153 27Ц5 15274 5Я644 12741 72И2 20354 02151+ 0.00000 00012 57!43 56106 0430Э 47Э74 77Я41 01Б12 63327+ 0.00000 00001 04560 27640 46655 12262 71426 40!24 21742+ 0.00000 00000 06676 ЯЯ766 ЭЫ67 55653 Я7265 34642 01627- 1.Ы404 74631 77167 46220 42627 бб!15 46725 !2575 174Я5+ 1.56663 65641 ЭО231 25163 54453 50265 60361,Э4073 42223— 2 17067 36ЯЯ4 57722 47602 57471 63003 00563 55620 320ИЗ.12305 40726 64ы5 22444 02242 57!01 4!466 зэ775 22532+ 1.20505 05746 15345 ОБЭ42 10756 65334 26674 224ЬБ 03024+ ! 342ЭЭ 50444 22175 731Я4 67363 76133 05ЯЯ4 ИЦ7 60121- 1.!4067 74050 61556!2455 72!52 64430 60271 02755 731Эб+ 0.5427! 02775 75071 73632 57Ц7 07316 30007 71эбб 53640+ !.06237 24752 55006 05227 32440 63065 й5012 35574 55337+ 2.2Я273 06735 Ы524 25405 56512 66542 56026 46050 50706+ 1.34252 16624 5Я405 77027 35750 Я7766 40644 35175 0435Э+ 0 ЯЯбйб 75425 11562 41614 52325 ЯЯ525 2765Б 14756 06220- Я 11037 5Ы42 10264 ЗОИ5 14230 63050 56006 70163 21!22+ О.о1огз 7иы 112И гйз44 йббоз 54276 63351 22056 ц544+ 0.24276 30155 62Я44 20251 2Я760 47257 50765 15156 70067— 11.
67517 Ц467 62135 71322 25561 15466 ЯООИ 40654 34103— 1.61337 64!06 64736 65247 47035 40510 1Ы73 34470 !7762— 2.5З347 35234 ио!з 61зьб 7з!об 476Ц 546ы оо!об 66046— !.26523 571 12 Ц154 74312 54572 Я7655 60126 23231 02452+ 2.55760 521ЗО 50535 и246 62773 42542 00471 72363 61661+ 0.27426 БЯОбб 13167 46761 52726 75436 02440 52Я71 ОЭЯ55+ 7.30714 45615 23355 33460 63507 35040 Я2664 25356 50217+ 0.44742 Ц770 67666 06172 2Я2!5 74376 01002 51313 255И— 1 11206 40443 47503 364!3 65374 52661 524!О 37511 46057+ !.47433 57156 277И 23701 27634 7140! 40271 66710 15010+ 1.61772 !3452 61152 65761 22477 365ы 5Яы7 17554 ийбо+ 2.Ц275 315ьй !6162 52Я70 35530 !!342 53525 44307 Ои7!— О 65665 24436 044Ц 73402 03067 23644 11Б12 07474 Ц505— О 42450 50037 32406 42711 07022 Цббб 27Я20 70675 12321+ О 7400! 45 Ц4 53253 42362 42107 23350 50074 46100 27706+ 1.
Ц735 0002Э 60014 20470 15613 42561 31715 10177 06614+ 0.36630 26256 61ИЯ 01Ц5 13700 41004 Ы264 30700 40646+ й.о4776 боьы !7!44 4!512 ц436 !6575 оозы 436эо 4оби+ 0.27351 71233 67265 63650 17401 56637 26334 ЗЦ55 57005— Значения некоторых констант с 40 знаками в табл. 1 вычислены на настольном калькуляторе Джоном у. Ренчем (мл.) (Зппп у1'.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
