Введение в прикладную комбинаторику, Кофман А. (984071), страница 5
Текст из файла (страница 5)
—, (7.2) и=О (7. 1) УПРАЖНЕНИЯ 6А. Пусть 7(х) = х'+ 1; вычислить ири Ь = 1: а) Е"1(х), и = 1, 2, 3; б) Дч) (х), л = 1, 2, 3. 66. Пусть 7(х) = хв; вычислить при Ь 1: а) ЛЕ)(х); б) ЛЧ)1(х); в) Ев Д()1(х). бв. Пусть 1(х) = 1/х; вычислить Да)(х). 6Г. Пусть 1(х) = з!и х; вычислить (х(!)в 1(х). 6Д. Доказать тождество 1'+ 2'+ ... + пв — (бп" + 15п' -1- 1Опв — 1), 30 6Е. Просуммировать (3' + 8) + (54 + 1!) + (7' + 14] + (9' + 17) + называемую отрицательным г-преобразованием.
Кроме того, как мы видели в $5, используется также функция с=с называемая экспоненциальным г-преобразованием. Эти функциональные преобразования применяются самым различным образом во многих областях: комбинаторике, теории вероятностей, математической статистике, электронике (импульсные режимы), исчислении конечных разностей, дискретных физических теориях и т. д.
Хотя в комбинаторике эти преобразования используются весьма специфически, нам кажется уместным напомнить здесь несколько свойств этого важного метода. (7.3) Рис. 6. Рис. 7. (7,4) Тогда 1*(г)= ~) г"= —, ь=с Итак, г-преобразованием для (7.4) будет П р и м е р 2 (рис.
7). Пусть 1, и = О, 1, 2, 1(п) = О, п=5,6,... (7.5) Ц1 — г). 3, 4, (7.6) Тогда Г*(з)= )~~ з"=~~ аь — ) "=~~а" — в У "= ~ . (7,7) с=а ь=с Для удобства последовательность а„, и = О, 1, 2, ..., будем обозначать через 1(п), и = О, 1, 2, ... Таким образом, при г-преобразовании 1"(п) будет соответствовать 1*(г) и обратно. Подобными обозначениями будем пользоваться и для других преобразований.
В настоящем параграфе будет рассматриваться только преобразование (7.1). Прежде чем перечислить некоторые его свойства, приведем несколько примеров. Приме р 1 (рис. 6). Пусть ~(п)=1, п=О, 1, 2, ... п=0,1,2, (7.8) Тогда М л (г) = ~1лпг = пг «~ пг'! ! =Йг — ~ г лга л=с л 0 (7.9) Раа 8 Р (п) = а" 1 (л), а еи К, Р (п) = л) (п) Р(п) = ~) 7(!) ИР (г)= с-о 1 О, и = О, 1, ..., Ф вЂ” 1, ! л Р(п) = ~ !(г) 8(л — г) Г 0 Р(п) =1(л+ 1) — )'(п) (7.17) (7.!8) Пример 3 (рис. 8). пусть )(и)=!сл, и аи К, Основные свойства 1(п) = г! (и) + ), (л) Р(л)=Ц(л), й~й, О, а=О. !(п — 1), л=1, 2, ...
Р (и) = 7" (п + 1) Р(п) = У(п+ й) 4Ф )'* (г) = !'! (г)+ Р; ( ), (7. 10) ФАР (г) = л7 (г), (7.11) ИР (г) = г1 (г), (7.12) < " (,) Р (г) — ПО) ФФР'(г) = г-л!'(г)— л-! — 2~ ) (г) г'-', (7.14) Г=л! ИР*(г) = 1" (аг), (7.15) ФФР'(г) = г 4 !" (г), (7,16) 44 Р"(г) = ~'(г) д"(г), (7.19) $Ф (г) = Р., (7.20) 1* (г) = г —, 8'(аг), с! гдв и(и)=по ', (7.36) 7'(п) = и~а", !' (г) = (!3 + аг)~, (7.37) 7(л) = !'(г) = — !п(1 — аг), (7.38) 1(л) = 1 (г) = Аг()! аг 1 1+ аг (7 39) = — !и— 2 1 — аг' О, 1(и)= а" О, ~(и) = оо и ' 1* (г) еос 1 (г)=айаг, (7.42) 1(п) = !(и) = 1(п) = 81пап, ! (и) совал, !' (и) = а-В" 84п ап, !с (л) = а-в" еоз аи, Формулы (7.45) — (7.48) останутся справедливыми, если заменить тригонометрические функции соответствуюшими гиперболическими.
28 С„а р" ", л=О, 1, ..., 1с, 0 л>(с, с О, п=О, — У, п=1,2,..., п четно, п иечетно, л = 0 или и иечетио и=2, 4, 6,..., и четно, и нечетко, и нечетно, л четно, !с* (г) = — — 1и (1 — асг'), 1 (7.40) (7.41) 1* (г) = сЬ аг, (7.43) 1'(г) = а', а > О, (7.44) гз1п а с' — 2гсооа+ 1 ' (7.45) 1 . г со5 о. г' — 2г сова+ ! (7.46) ~~(г) = гно а о Вг~ — 2г соса+ оа ' (7.47) с*( ) а — з сова Р а "г~ — 2гсоза+аа ' (7.48) Обратное преобразование.
Коэффициенты разложения /'(г) в ряд Тейлора образуют исходную последовательность /(и). Теория интегрирования функций комплексной переменной на плоскости г х+ !у с помощью вычетов дает возможность получения коэффициентов этого ряда. Если /*(г) — рациональная дробь, каждый из полюсов которой по модулю больше или равен 1, то можно получить удобные формулы. Пусть (7.49) — рациональная дробь, причем полиномы и(г) и о(г) не имеюг общих корней.
Предположим, что степень полинома и(г) меньше степени полннома о(г) (в противном случае достаточно заменить г на !/г) и что корни 1/а!, !/им ..., 1/аь полинома о(г) по модулю больше или равны 1, т. е. что !а!~ ( 1, / = = 1, 2, ..., 1.. Известно, что такую рациональную дробь можно разложить на простые дроби, а именно ! р! /*(')=Х ~~, -~ ~~ ~ (! а,г) (7.50) где Р! — кратность корня 1/аь Учитывая (7.10), (7.1!) и (7.30), из (7.50) получаем обратное преобразование: ь '! ь /(и) = ~!,~~ Сп+р !Арпа! = Х В;(п)а";, а=О, 1, 2, ..., (7,5!) !=! р=! !=! где Р! В! (и) =,~~ С„".р !А (7.52) р — ! ! Представить коэффициенты В!(и) в виде функции от полиномов и(г) и о(г), вообще говоря, сложно; однако отметим, что если а! (например) — простой корень о(г), т. е.
Р, = 1, то В! (и) = С„"А!! = А!!. (7.53) Далее, если положим о (г) = (1 — а, г) а! (г), (7.54) то, сравнивая (7.49) и (7.50), имеем В,(п)=Ац — — ' — — — а,, ' = !!ш (! — а,г)/*(г), (7.55) где о'(г) обозначает производную от о(г) по г. Замечание. г-преобразование приводит, в сущности, к некоторому «символнческому исчислению» или «операционному исчислению», аналогичному тому, которое получается с помощью 29 преобразования Лапласа (нли Карсона — Лапласа, если угодно) для функций, непрерывных на отрезках, хотя г-преобразование и применяется к последовательностям.
Как уже отмечалось, г-преобразование — это не что иное, как особое представление производящей функции, в наибольшей степени используемое в теории вероятностей, Как г-преобразование, так и само преобразование Лапласа восходят к Эйлеру и Лапласу. Некоторые свойства преобразования Лапласа: 7„(р)= ) е ''1(~)Ж (ен)с+, Пер)со>0, (7.56) о легко переносятся на г-преобразование: )*(г) = ~1(п) г" при замене р на 1 — г.
Заметим также, что преобразованию Карсона — Лапласа ) „(р)=р) е ~~(~)Ф, (~ )х~, Кер- 'со> О, (7.58) о можно сопоставить видоизмененное г-преобразование 7' (г) = (1 — г) ~ 7 (и) г", (7.59) о-о при этом некоторые формулы упрощаются. Пример применения г-преобразования к уравнениям в конечных разностях. Рассмотрим уравнение в конечных разностях )(и+2) — ~(п+1) — ~(п)=0, п=О, 1, 2, ..., (7.60) с )(0)=ао и ((1)=ао (7.61) Применяя (7.13) к ((и+1), а затем к ((п+ 2), имеем 1" ( ) — 1(о) — 1(П 7'(г) = 0 (7,62) нли Г (г) — аю — а~г )" (г) = О, (7.63) откуда ао + (а~ — ао) г (7.64) Представляя 1 — г — г' в виде 1 —.—" =(!в 1+3/5 ) 1 ! — )75 2 г), (7.66) имеем )75 1 ! +3~5 2 Используя (7.27), получаем Другие важные соотношения.
Пусть а'(г) =,. (,) (7.68) Тогда ) (0) д (0) = 1, 1 (О) д (1) + 7 (И д (О) = О, 7(0) д (2) + ~ (1) л (1) + )(2) д (0) = О, (7.69) а (0) = 1(0), 1 откуда 1(1) 87 (1) = !1(0)]7 11(1)] 1(2) и т а( ) [1(0)]3 ]1(0))7 (7.70) Р (и) =,',~ ~ (г) а (и — х) 4Ф Р* (г) = ~' (г) д' (г). (7.71) Если рассмотрим три последовательности, связанные между собой соотношением (7.71), то задание двух из этих последовательностей определяет третью.
По внутреннему закону композиции, 51 Вообще, исходя из (7.19), имеем )75+ 1 (7.66) ! — г 2 определяемому формулой (7.7!), можно указать некоторый об- ратный внутренний закон. Относительно первого последователь- ности образуют группу "), а относительно второго не образуют группы ,г, !"*(г) = )~~г(г — 1)1(г) г' -', Г=! (7.72) пь — „1' (г) = ~ г (г — 1)...
(г — lг + 1) 1 (т) г'-ь к=ь или г ~ 1 (г) = у г) (г) г', !12 г' зг, !"' (г) = ~ г (г — 1) 1 (г) г', г=! (7.73) г~ †„ Ч (г) = ,~~ т (т — 1) ... (т — й + 1) 1(г) г" = ~~ Аь( (г) г'. г=ь г=ь Экспоненциальное г-преобразование.
Можно показать, что это преобразование обладает свойствами, подобными свойствам, которые были установлены для обычного г-преобразования. Вот некоторые из них; т О, п=О, 1 )(и — !), п=1, 2...,, Р(п) =1(и+ 1), п=О, 1, 2, ...,4$Р'(г) = — !'(г)„(7 77) ") 10зьо. (!7рим, ред.) 32 ~(~) =(,(~)+ ~,( ) Р(п)=л1(п), леБК, 4$ (' (г) = ~; (г) + ~; (г), (7.74) (фр'(г) = Ц'(г), (7.75) Р (п) = и) (п) Й2 Р(п) а"1 (п) Ю Р'(г) =Г'(аг), О, п = О, 1, 2, ..., й — 1, Р (п) - Цп А), . А, А + 1, ..., ФФР (') = Е Ф г = ) ) ... ) )'(г) Ыг, (7.80) о а о Р(п) = Х7" («) а(п — «)ФФР'(г) =1'(г) а'(г), (7.78) (7.79) (7.81) т 0 Р (п) = ~ (п + 1) — ~ (п) 44 Р' (г) = — 1'(г) — 1'(г).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
