суммы
аn xn + bn xn = (аn + bn) xn ,
( аn / n!) xn + ( bn / n!) xn = [ (аn + bn) / n!] xn;
произведения
аn xn × bn xn = kn xn , где kn = 
аi bn-i,
( аn / n!) xn × ( bn / n!) xn = ( dn / n!) xn, где dn = Cni аi bn-i;
умножения на скаляр
a аn xn = a аn xn , a ( аn / n!) xn = (a аn / n!) xn для "aÎ R.
Вычитание двух ФСР определим, как сложение первого ряда со вторым, помноженным на (−1).
Ноль-ряд − тот, у которого аn = 0 для n = 0, 1, 2, …; единица-ряд − тот, у которого а0 = 1, аn = 0 для n = 1, 2, …
Пусть A − множество всех ФСР вида аn xn, Aе − множество всех ФСР вида ( аn / n!) xn. Алгебра (А, +, ×, −, 0, 1) наз. алгеброй отношений; алгебра (Aе, +, ×, −, 0, 1) наз. биномиальной алгеброй.
Теорема. Биномиальная алгебра и алгебра отношений являются целостными кольцами.
Композиция ФСР
Теорема. Если а0 = 0, то выражение: bn (
аk xk) n является формальным степенным рядом.
Обратимость ФСР
Ряд bn xn называется обратным к ряду аn xn, если их произведение равно 1.
Теорема. Ряд, обратный к ряду аn xn существует, тогда и только тогда, когда а0 ¹ 0.
Чтобы найти обратный ряд, надо
составить вспомогательный ряд g(x) = 1 − (1/ а0) аn xn; обратный ряд найти по формуле: ( аn xn)−1 = (1/ а0) (1 + g(x) + g2(x) +… ). Деление двух ФСР определим, как умножение первого ряда на ряд, обратный ко второму (если обратный существует).
Аксиомы
аn xn = (n+1) аn+1 xn, ( аn / n!) xn = ( аn+1 / n!) xn .
интегрирования
ò (аn xn ) dx = 
( аn−1 / n) xn, ò ( ( аn / n!) xn ) = ( аn−1 / n!) xn .
Для ФСР выполняются все элементарные свойства производных.
§ 3. Операции над производящими функциями
Основной принцип теории производящих функций: пусть имеется некоторое равенство, содержащее степенные ряды, которое выполняется, если считать ряды сходящимися в некоторой окрестности нуля. Принято считать, что это равенство остаётся верным, если его рассматривать как соотношение между ФСР (лишь бы операции, участвующие в равенстве, имели смысл для ФСР).
Операции над производящими функциями
1. Линейные. Пусть a, b Î R.
( c(n) = a a(n) + b b(n) ) ® ( c(x) = a a(x) + b b(x), ce(x) = a ae(x) + b be(x) ).
2. Изменение масштаба.
( b(n) = n a(n) ) ® ( b(x) = xa(x), be (x) = xae (x) ).
3. Сдвиг начала.
а) b(n) = 
® b(x) = a(x) xk, be(x) = òò…ò ae(x) dx (k раз).
б) b(n) = a(n+k) ® b(x) = [ a(x) − 
аi xi ] x−k, be(x) = 
ae (x).
4. Подобие. Пусть a Î R.
( b(n) = an a(n) ) ® ( b(x) = a(ax), be(x) = ae(ax) ).
5. Свёртка.
( kn = аi bn-i ) ® ( k(x) = a(x) × b(x) ).
Таблица простейших производящих функций
№ п/п | аn | а(x) | аe(x) |
1 | 1 | 1 / (1−x) | ex |
2 | a n | 1 / (1−ax) | eax |
3 | 1 / n! | ex | − |
4 | a n / n! | eax | − |
5 | Can | (1+x) a | − |
6 | C n n+ b −1 | (1−x) −b | − |
7 | a n C n n+ b −1 | (1−ax) −b | − |
8 | n | x / (1−x)2 | x ex |
§ 4. Производящие функции числа основных комбинаторных объектов
4.1. Сочетания
Пусть М = {e1, e2, … em}.
Рассмотрим произведение: (1+ e1x) (1+ e2x) … (1+ em x) = 1 + x (e1+ e2 + … + em) +
+ x2 (e1e2 + e1e3 + … + em−1 em) + … + xm e1 e2 … em.
Каждое слагаемое коэффициента при xk соответствует одному сочетанию.
Положим e1 = e2 = …= em = 1, получим:
(1+x) m = Cm0 + Cm1 x + Cm2 x2 + … + Cmm xm.
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 11 12 |
Основные порталы (построено редакторами)