Д. Кнут - Искусство программирования том 1 (1119450), страница 26
Текст из файла (страница 26)
Бос. 25 (1923), 135-154; 1еап Нггеп, АММ 76 (19б9), 871 — 889; Ресег Неппс!, Арр!ж3 апс1 Сотри1айопа1 Сотр!ех Апа(уяа 1 (%11еу, 1974), Сбарсег 1. А теперь давайте рассмотрим основные методы работы с производящими функциями. А. Сложение. Если С(з) — производящая функция для (о„) = оо,ам... и Н(з)— производящая функция для (Ьь) = Ьо,Ьм..., то аС(з) + ДН(з) — производящая функция для (аа„+ ~ЗЬ„) = аао + ~ЗЬо, аа1 + бЬм....
а ~ а„з" +,9 ~ 6„з" = Я (ао„+ рЬ„)з". ь>0 ьйо В. Сдвиг. Если С(г) — производящая функция для (а„) = ао,ам..., тол С(з)— производящая функция для (а„) = О,..., О, оо, а1„..... а„з = ~а„„,г . ю~ я ь ь>0 г ~~ о„з"=~ а„е з". ь>0 В предыдущем разделе для решения задачи Фибоначчи мы комбинировали операции А и В: С(г) была производящей функцией для (Р;,), гС(с) — для (Р„1), гзС(з) — для (г' з), а (1 — з — гэ)С(з) — для (гь — г'„-1 — г'„з). Затем, так как разность г„— Е„1 — г'„з равна нулю при и > 2, мы выяснили, что (1 — г — зз)С(з)— это многочлен. Аналогично производящая функция для любой линейной рекурреитпиой последовательности (т. е. такой последовательности, для которой а„ = с1а„1+ + с„,о„) является многочленом, деленным на (1 — с1г — — с,ьса).
Давайте рассмотрим простейший пример. Если С(з) — -производящая функция для постиояииой последовательности 1, 1, 1,..., то зС(з) порождает последовательность О, 1, 1,..., поэтому (1 — г) С(г) = 1. В результате получаем простую, но очень важную формулу: — =1+з+г +. 1 2 (б) 1 — з С. 'Умножение. Если С(з) — производящая функция для ао,ам... и Н(з)— производящая функция для 6о,6м., ., то С(х)Н(з) = (по+ а1з+ аз» + )(Ьо+ Ьгз+Ьзгз+...) = (ооЬо) + (аоЬ1 + агЬо)з + (аоЬз + агЬ! + озЬо)з~+ С(г)Н(г) — производящая функция для последовательности се, Следовательно, см..., где с„= ~~~ аьЬ„ы азин (6) В сумме справа суммирование можно распространить на все и > О, если считать, что а„= О для любого отрицательного и.
Аналогично (С(з) — оо — а1 з — ° — а ~вы ~)/㙠— производящая функция для (о~+~) = от~от+и Соотношение (3) является частным случаем (6). Другой важный частный случай имеет место, когда все 6„равны единице: 1 — С(з) = ао + (ао + а1)з + (ас + а1 + аг)зз + (7) 1 — з Здесь мы получаем производящую функцию для частных сумм исходной последовательности. Из соотношения (6) следует правило для произведения трех функций; Р(з) С(з) Н(г) порождает последовательность 4„4, Нз,..., где г(„= ~~~ а;6,сь. (8) ол>о з ьз.~-э=и Общее правило для произведения любого числа функций (в тех случаях, когда это имеет смысл) выглядит следующим образом; П ~~' азь~ = ~з" ~ ась,аыч ....
(О) 1>о ь>о в>о з.,ь,...,>о зг+ач+- = Когда в рекуррентном соотношении для некоторой последовательности содержатся биномиальные коэффициенты, часто возникает необходимость в получении производящей функции для последовательности со,сы..., которая определяется формулой с„= ~ ( )аь6„ы (10) (См. упр. 14.) Например, если т = 3 и г = 1, то и = — — + — з (комплексный кубический корень из единицы). Отсюда следует, что агз+а4з +агз + = -'(С(г)+ы С(юз)+а С(ы з)). В этом случае, как правило, лучше воспользоваться производящими функциями последовательностей (а„/и!), (6„/и!), (с„/и!), поскольку (. .
. Н . . . )=(. . . ) аэ а1 аз з ~76с 6з 6з з '1 /со сз сз з — + — г+ — з + — + — 3+ — з + ) = ( — + — 3+ — 3 +, (11) 0', 1! 2! / 1 О! П 2! ) 1 О! 1! 2! где с„определяется формулой (10). Р. Замена переменной в. Очевидно, что С(сз) — производящая функция для последовательности ас, сам сзаз,.... В частности, пРоизводЯщей фУнкцией длЯ последовательности 1, с, сз, сз,...
является 1/(1 — сз) . Воспользуемся известным приемом для извлечения членов ряда через один: -(С(з) + С(-з)) = ао + аззз + агзз + (12) з(С(г) С(-з)) = азз + аззз + аззз + Извлекая комплексные корни из единицы, можно развивать эту идею и выбирать каждый т-й член. Пусть и = ез"7' = соз(2л/т) + з з!п(2х/т). Тогда а„з" = — ~~ ы ь"С(ызз), 0 < т < т. 1 (13) и тод п~=~ о<э< Е. Дифференцирование и интегрирование.
С помощью методов дифференциального и интегрального исчислений можно выполнять над производящими функциями дополнительные операции. Если С(») определяется формулой (1), то ее производная равна С (») = ак + 2аг» + Заз»г + ° = "~ (е + 1)ак~кк»". (14) к>о Производящей функцией для последовательности (па„) является»С'(»). Следовательно, выполняя операции над производящей функцией, мы можем найти производящую функцию для последовательности, полученной из предыдущей умножением каждого члена а„на многочлен от и. Обратный процесс, т.
е. интегрирование, дает еще одну полезную операцию: С(Ф)й = ао»+ -а~» + — аг» + = ~~ — ак к» . г 1 3 1 к 2 3 )о (15) В качестве частных случаев возьмем производную и интеграл от функции (5): 1 (1 — »)г =1+ 2»+ 3»г+ = ~~~ (1+1)»"; (16) к>о 1п — =»+-» +-» + .= у -». г 1г т 1к М 1 — » 2 3 ~к к>1 (1+») =1+т»+» +.-.=~ ~ )», т(т — 1) г /т'к 2 к>о (19) Если т — неотрицательное целое число, то получаем частный случай, который уже отражен в соотношениях (5) и (16): (20) Существует также обобщенная формула, доказанная в упр.
1.2.6 — 25: т(т — 21 — 1) . тт — Й~ т и" = 1+г»+ »г+ =Я ) — "; у.-и к>о Сопоставляя (17) и (7), найдем производящую функцию для последовательности гармонических чисел: — 1и — =»+ -» + — » + = у Нк» . 1 †» 1 †» 2 6 к>о Р. Известные производящие функции. В каждом случае, когда функция разлагается в степенной ряд, мы, по сути, получаем производящую функцию для некоторой последовательности. Эти специальные функции могут быть очень полезны в сочетании с операциями, описанными выше. Ниже приведены самые важные случаи разложения в степенной ряд. 1) Биномиальнал теорема. с.
представление коэффициента. Для коэффициента при 2" в выражении для С(2) часто удобно использовать запись [2"[О( ). (31) Например, если С(2) — производящая функция, определяемая формулой (1), то [2"]С(2) = а„и [2"[С(2)/(1 — 2) = 2 ь еаы Одним из самых фУндаментальных результатов теории комплексного переменного является формула О. Л. Коши (А. Ь. Свисту) [Ехегс1сеэ с(е Масй. 1 (1826), 95 — 113 = СЕиггеэ (2) 6, 124-145, Е11.
(11)[, по которой любой нужный коэффициент можно представить в виде интеграла по контуру 1 ~ С(2) ЫЭ 2я1,/~,~, 2""1 (32) если С(2) сходится для 2 = Эе и О < г < [зо[. Главная идея состоит в том, что интеграл у,, 2 ~Ь равен нулю для всех целых т, за исключением т = — 1, когда интеграл равен /. " ' ' = /. = я (ге1 ) 1<((ге1 ) =1 / се = ия1. Рассмотрим общий случай. Пусть есть и чисел х1„хз,...,х„и нужио найти сумму Ь = ~1 х11 ...к 1<1 «" 1 <и Требуется, если возможно, выразить эту сумму через 51, 52, ..., Я, где (33) Я = 2 хь 1=1 (34) представляет собой сумму 1-х степеней. Используя эту более компактную запись, можно переписать приведенные выше формулы следующим образом: ~Э вЂ” эЕ1 + 2Е1Е2 + Э~Э. Ьг = 5 ~1 + йй2 1 2 1 Чтобы решить задачу, рассмотрим производящую функцию С(2) = 1+512+522 +''' ~~~ йье (35) ь>о Формула (32) особенно важна в случае, когда мы хотим изучить поведение коэффициента.
И в заключение раздела вернемся к задаче, которая была лишь частично решена в разделе 1.2.3. Из формулы 1.2.3 — (13) и упр. 1.2.3 — 29 следует, что Согласно правилу умножения рядов находим С(с) =(1+х~г+х,х + )(1+хаю+х~~г + )...(1+х„г+х„г + .) (36) (1 — х~г)(1 — хтл)... (1 — х г) Таким образом, С(г) — это величина, обратная многочлену. Во многих случаях бываег полезно прологарифмировать произведение; сделав это и воспользовавшись формулой (17), получим 1пС(а) =!и + . +1п 1 1 1 — х~г 1 — х„т (37) Таким образом, мы выразили 1п С(э) через Вы Й > 1.
Теперь для получения окон- чательного ответа осталось найти разложение С(г) в степенной ряд с помощью (22) и (9): С(в) = еыО(') = ехр(~ — ) = Ц ез"' /ь ~„~й т ь>1 ь>1 2 Й ) — П Ф" 1"'Й1' 2"'Й2' гп "Йь! ) >о ь„ь„ д >о (38) в~+та~+ +~ьь =из Величина в круглых скобках — Й . Эта внушительная сумма при внимательном рассмотрении оказывается не такой уж сложной. Число членов для конкретного значения гп равно р(т), т. е.
числу разбиений гп (см. раздел 1.2.1). Например, одним из разбиений числа 12 является 12=5+2+2+2+1; 81 В2 оь 1 3 — В!отав 1)1~ 2з3~ 5)1~ 240 который является частью выражения для Ьпь Дифференцируя (37), нетрудно получить рекуррентное соотношение 1 Йь (ЯЙп-1 + Ж~п-2 + ' '+ БпЙО)~ и > 1. (39) п Замечательное введение в теорию применений производящих функций можно найти в книге О. Р61уа, Оп рксиге ит111л8, АММ 63 (1956), 689-697; этот подход это соответствует некоторому решению уравнения Й~ + 2Йт + . + 12Йю — — 12, где Й, — количество слагаемых в разбиении, равных (. В нашем примере Й~ = 1, Йт = 3, Йь = 1, а все остальные Й, равны нулю, поэтому получаем член был использован в СМаг)з, СЬаргег 7.
[См. также книгу Н. Б. 1У()г", Сепета6пбйпс- г)опо)оЯу, весош( еб(г)оп (Асаг)ет!с Ргевв, 1994).] ПРОИЗВОДЯЩЭЯ фУнкция — Зто бельевая веревка, на которую мы вывешиваем последовательность чисел ДЛЯ ВСЕОбЩЕгО ОбозреккЯ вЂ” Г. С. ВИЛЬаз (Н. 5. ЗЛЛ Е) (1989) УПРАЖНЕНИЯ 1. [М1Я] Найдите производящую функцию для последовательности 2, 5, 13, 35, (2»+ 3») 2. [М15] Докажите формулу (11). 3. [НМЯ1] Продифференцируйте производящую функцию (18) для последовательности (Н ) и сравните результат с производящей функцией для последовательности Щ Нз).
Какую связь между ними вы обнаружили? 4. [МО1] Объясните, почему (19) является частным случаем (21). 5, [МЯО] Докажите (23) индукцией по гг 6, [НМ15] Найдите производящую функцию для последовательности продифференцируйте ее и выразите коэффициенты через гармонические числа. 'Т. [М15] Проверьте все этапы вывода соотношения (38) 8. [МЯЗ] Найдите производящую функцию для последовательности р(п) — числа разбиений целого и. 9. [М11] Используя обозначения из соотношений (34) и (35), выразите 1зз через Ян лз, оз и оз ь 10.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
