Согласно правилу умножения рядов находим

Giz) = (1 + xiz + x\z + • • • )(1 + + x\z + ••)-. (1 + a;„z + xz + • •)

" {l-xiz){\-X2z)...{\-Xnzr

Таким образом, G{z)-это величина, обратная многочлену. Во многих случаях бывает полезно прологарифмировать произведение; сделав это и воспользовавшись формулой (17), получим

InG(z) =1п

1 - X\Z

+ • +In

1 - XnZ

(37)

Таким образом, мы выразили lnG(2;) через 5, к > 1. Теперь для получения окончательного ответа осталось найти разложение G{z) в степенной ряд с помощью (22) и (9):

Skz"

G(z) = е-«() = ехр(5: ) = П в-*/*

:b(l + 5lZ+ + ..

-е( е

т>0 V ki,k2, ,*m>0

1 + +

2 22-2! 5* 5

.>о

ki+2k2+ +тк,п=т

1*1 fci! 2*=fc2! ткш\)

(38)

Величина в круглых скобках - hm- Эта внушительная сумма при внимательном рассмотрении оказывается не такой уж сложной. Число членов для конкретного значения т равно р{т), т. е. числу разбиений т (см. раздел 1.2.1). Например, одним из разбиений числа 12 является

12 = 5 -Ь 2 -Ь 2 4- 2 -Ы;

это соответствует некоторому решению уравнения fci -Ь 2А;2 -Ь • • • -Ь 12A;i2 = 12, где kj -количество слагаемых в разбиении, равных j. В нашем примере ki = 1, А;2 = 3, А;5 = 1, а все остальные kj равны нулю, поэтому получаем член

5i 5 55

S\SlSb,

1U! 233! 54! 240

который является частью выражения для hi2- Дифференцируя (37), нетрудно получить рекуррентное соотношение

hn = -(5i/i„ i + S2hn~2 +----1- Snho), п>1.

Замечательное введение в теорию применений производящих функций можно найти в книге G. Polya, On picture writing, AMM 63 (1956), 689-697; этот подход

был использован в CMath, Chapter 7. [См. также книгу Н. S. Wilf, Generatingfunc-tionology, second edition (Academic Press, 1994).]

Производящая функция-это бельевая веревка, на которую мы вывешиваем последовательность чисел

для всеобщего обозрения

- Г. С. ВИЛЬФ (Н. S. WILF) (1989)

УПРАЖНЕНИЯ

1. [М12] Найдите производящую функцию для последовательности 2, 5, 13, 35,... (2" + 3").

► 2. [М13] Докажите формулу (11).

3. [НМ21] Продифференцируйте производящую функцию (18) для последовательности (Нп) и сравните результат с производящей функцией для последовательности {J2k=ai)-Какую связь между ними вы обнаружили?

4. [М01] Объясните, почему (19) является частным случаем (21).

5. [М20] Докажите (23) индукцией по п

► 6. [НМ15] Найдите производящую функцию для последовательности

o<V<„

продифференцируйте ее и выразите коэффициенты через гармонические числа.

7. [М15] Проверьте все этапы вывода соотношения (38)

8. [М23] Найдите производящую функцию для последовательности р{п) -числа разбиений целого п.

9. [ми] Используя обозначения из соотношений (34) и (35), выразите hi через Si, 52, 5з и 54

► 10. [М25] Элементарная симметричная функция определяется по формуле

От = Y

1<Л< <Jm<n

(Это то же самое, что и km из (33), только при суммировании не допускается равенство индексов ) Найдите производящую функцию для последовательности ащ и выразите ащ через 5j, определяемые формулой (34) Выпишите формулы для oi, 02, 03 и 04

► 11. [Мй5] Соотношение (39) можно также использовать для того, чтобы выразить Sk через Нк находим Si = кг, S2 = 2/i2 - hi, S3 - 3/гз - 3/ii/i2 -Ь /г? и т д Чему решен коэффициент при /г* /13 /г"" в таком представлении 5ш, если fci -- 22 + + ткт =

► 12. [М20] Пусть у нас есть последовательность с двумя индексами атп, где т, п = 0,1, Покажите, что эту последовательность можно предсташить с помощью одной производящей функции двух переменных, и найдите производящую функцию для последовательности

атп = {)

13. [НМ22] Преобразованием Лапласа функции f{x) называется функция

Lf{s)= Г e-4it)dt Jo

Пусть ao,ai,a2,...-бесконечная последовательность, производящая функция которой сходится, и пусть /(х)-ступенчатая функция J2k o,k[Q<k<х]. Выразите преобразование Лапласа функции /(х) через производящую функцию G заданной последовательности.

14. [НМ21] Докажите соотношение (13).

15. [МЙ5] Рассмотрим функцию Н(и;) = 53„>о "(•)"- Найдите замкнутую форму для производящей функции

к=0 " *=0 "

16. [М22] Найдите простую формулу для производящей функции Gnriz) = Yk°"lrZ, где йпкг - количество способов выбора к объектов из п при условии, что каждый объект можно выбрать максимум г раз. (При г = 1 получаем () способов, а при г > к - число сочетаний с повторениями, как в упр 1 2 6-60.)

17. [М£5] Найдите коэффициенты в разложении функйии 1/(1 -г)" в двойной степенной ряд по г и и;

► 18. [Мй5] Для заданных положительных целых чисел п и г найдите простые формулы для следующих сумм: (а) T,i<k<k2< <*.<n*i2 -fcr, (b) Ei<*i<*,< <*„<„fcifc2...fcr. (Например, для n = 3 и г = 2 эти суммы соответственно рашны 1 2--1-3--2-Зи l-l--l-2-fl-3--2-2--2-3--3-3.)

19. [НМ32] (К Ф Гаусс (С F Gauss), 1812 ) Хорошо известны суммы следующих бесконечных рядов:

с помощью определения

п>1

данного в ответе к упр. 1.2.7-24, эти ряды можно переписать следующим образом соответственно- 2 11 11

1-21/2; 3 - Я1/4-1--Яз/4, J-gЯl/6--gЯ2/з. Докажите, что в общем случае значение Яр/, равно

Я , п , п 2pfc , . к

--- cot-7г - 1п2д-Ь 2 > cos-7r-lnsm-7r,

р 2 g /L д д

0<k<q/2

где р и q - целые числа и О < р < 5 [Указание. По теореме Абеля эта сумма равна

п>1

- frfV" n + p/qj

С помощью соотношения (13) выразите этот степенной ряд таким образом, чтобы можно было вычислить предел ]

20. [М21] Для каких коэффициентов Cmfc справедливо равенство

Y,n-z"=Yc,nkz/{l-zr?

п>0 к=0