Изменения

''Суммой'' {{Лемма|statement = Пусть <tex>A(s) = a_0 + a_1 s + a_2 s^2 + a_3 s^3 + \dots </tex> {{---}} формальный степенной ряд, причем <tex>A(0) \ne 0</tex>. Тогда существует единственный обратный по умножению к <tex>A(s)</tex> ряд <tex>B(s) = b_0 + b_1 s + b_2 s^2 + b_3 s^3 + \dots </tex> и .|proof = :Распишем <tex>A(s)B(s)</tex> называется ряд по формуле произведения рядов: <tex>A(s) + B(s) = a_0 b_0 + (a_0 b_1 + a_1 b_0) s + (a_0 b_2 + a_1 b_1 + b_1a_2 b_0) s ^2 + \dots</tex>. Заметим, что условие <tex>A(s)B(a_2 + b_2s) = 1</tex> выполнено только в том случае, если <tex>a_0 b_0 = 1</tex>, а все остальные слагаемые полученного ряда равны нулю. :Докажем по индукции, что такой ряд <tex>B</tex> единственен. Нам известно, что <tex>b_0 = \dfrac{1}{a_0}</tex>. Пусть теперь все коэффициенты ряда <tex>B</tex> вплоть до степени <tex>n - 1</tex> однозначно определены. Коэффициент при <tex>s^2 n</tex> определяется из условия <tex>a_0 b_n + a_1 b_{n - 1} + \dots+ a_n b_0 = 0</tex>. Это линейное уравнение на <tex>b_n</tex>, причем коэффициент <tex>a_0</tex>при <tex>b_n</tex> отличен от нуля. Такое уравнение имеет единственное решение.}}

{{Определение|definition='''Делением'''Произведением(англ. '' division'') формальных степенных рядов <tex>A(s)</tex> и <tex>B(s)</tex> называется ряд операция <tex>\dfrac{A(s)}{B(s) } = a_0 b_0 + A(a_0 b_1 + a_1 b_0s) B(s + )^{-1}</tex> (при условии существования у <tex>B(a_0 b_2 + a_1 b_1 + a_2 b_0s) s^2 + \dots</tex>обратного).}}

Операции сложения и умножения формальных степенных рядов коммутативны и ассоциативны===Примеры===#Допустим, надо построить обратный ряд для <tex>A(s) = 1 + s</tex>.Воспользуемся леммой:#:<tex>b_0 = \dfrac{1}{a_0} = \dfrac{1}{1} = 1</tex>#:<tex>a_0 b_1 + a_1 b_0 = 0 \Rightarrow b_1 = - \dfrac{a_1 b_0}{a_0} = - \dfrac{1 \cdot 1}{1} = -1</tex>#:<tex>a_0 b_2 + a_1 b_1 + a_2 b_0 = 0 \Rightarrow b_2 = - \dfrac{a_1 b_1 + a_2 b_0}{a_0} = - \dfrac{1 \cdot (-1) + 0}{1} = 1</tex>#:<tex>\dots</tex>#:<tex>b_n = - \dfrac{a_1 b_{n - 1}}{a_0} = -b_{n - 1}</tex>#:<tex>B(s) = 1 - s + s^2 - s^3 + \dots</tex>#Пусть теперь надо построить обратный ряд для <tex>A(s) = 1 - s - s^2</tex>:#:<tex>b_0 = \dfrac{1}{a_0} = \dfrac{1}{1} = 1</tex>#:<tex>b_1 = - \dfrac{a_1 b_0}{a_0} = - \dfrac{(-1) \cdot 1}{1} = 1</tex>#:<tex>b_2 = - \dfrac{a_1 b_1 + a_2 b_0}{a_0} = - \dfrac{(-1) \cdot 1 + (-1) \cdot 1}{1} = 2</tex>#:<tex>b_3 = - \dfrac{a_1 b_2 + a_2 b_1}{a_0} = - \dfrac{(-1) \cdot 2 + (-1) \cdot 1}{1} = 3</tex>#:<tex>\dots</tex>#:<tex>b_n = - \dfrac{a_1 b_{n - 1} + a_2 b_{n - 2}}{a_0} = b_{n - 1} + b_{n - 2}</tex>#:<tex>B(s) = 1 + s + 2 s^2 + 3 s^3 + \dots</tex>

{{Определение|id=def_in|definition = '''Композицией (подстановкой)'' ' (англ. ''composition'') формальных степенных рядов <tex>A</tex> и <tex>B</tex> называется формальный степенной ряд <tex>A(B(t)) = a_0 + a_1 b_1 t + (a_1 b_2 + a_2 b_1^2) t^2 + (a_1 b_3 + 2 a_2 b_1 b_2 + a_3 b_1^3) t^3 + \dots</tex>.}}

Операция подстановки в случае, когда <tex>B(0) \ne 0</tex>, не определена. (При попытке подставить такой ряд для вычисления коэффициентов результата возникает необходимость суммирования бесконечных числовых рядов).

==Обратная=={{Теорема |about = об обратном формальном степенном ряде|statement = Пусть Обратный ряд <tex>B(t) = b_0 + b_1 t + b_2 t^2 + b_3 t^3 + \dots</tex> таков, что <tex>B(0) = b_0 = 0</tex>, а <tex>b_1 \ne 0</tex>. Тогда существуют такие ряды <tex> A(s) = a_1 s + a_2 s^2 + a_3 s^3 + \dots</tex>, <tex>A(0) = 0</tex> и <tex>C(u) = c_1 u + c_2 u^2 + c_3 u^3 + \dots</tex>, <tex>C(0) = 0</tex>, что <tex>A(B(t)) = t</tex> и <tex>B(C(u)) = u</tex>. При этом, ряды <tex>A</tex> и <tex>C</tex> единственны.

Производящие функции, соответствующие рядам '''Левым обратным''' (англ. ''left inverse'') по операции подстановки формальным степенным рядом для ряда <tex>B(t)</tex> называется такой ряд <tex>A(s)</tex> и , что <tex>CA(B(t)) = t</tex>. Аналогично, называется соответственно '''левойправым обратным''' и (англ. ''right inverse'правой обратной''' к производящей функции) формальным степенным рядом для <tex>B(t)</tex> называется такой <tex>C(u)</tex>, соответствующей ряду что <tex>B(C(u)) = u</tex>.

:Докажем по индукции существование и единственность левой обратной функциилевого обратного ряда. Доказательство для правой обратной правого аналогично. :Будем определять коэффициенты ряда <tex>A</tex> последовательно. Коэффициент Поскольку <tex>a_1A(B(t)) = t</tex> определяется из условия , <tex>a_1 b_1 = 1</tex>, откуда <tex>a_1 = \dfrac{1}{b_1}</tex>. Все остальные коэффициенты результирующего ряда при этом равны нулю. :Предположим теперь, что коэффициенты <tex>a_1, a_2, \dots, a_n</tex> уже определены. Коэффициент <tex>a_{n+1}</tex> определяется из условия <tex>a_{n+1} b_1^{n+1} + \dots = 0</tex>, где точками обозначен неокторый некоторый многочлен от <tex>a_1, \dots, a_n</tex> и <tex>b_1, \dots, b_n</tex>. Тем самым, условие представляет собой линейное уравнение на <tex>a_{n+1}</tex>, причем коэффициент <tex>b_1^{n+1}</tex> при <tex>a_{n+1}</tex> отличен от нуля. Такое уравнение имеет единственное решение, и теорема доказана.

==Деление=={{ЛеммаСдвиги могут быть полезны для упрощения вычисления производящих функций.|about = деление формальных степенных рядов|statement = Например, попробуем получить функцию для чисел Фибоначчи, используя сдвиги. Пусть формальный степенной ряд для нее равен <tex>AF(s) = a_0 f_0 + a_1 f_1 s + a_2 f_2 s^2 + a_3 s^3 + \dots </tex> , при этом <tex>f_0 = f_1 = 1</tex>, <tex>f_n = f_{n - 2} + f_{n ---1}} формальный степенной ряд, причем n > 1</tex>. Рассмотрим сумму этого ряда и ряда, полученного из него сдвигом на <tex>A(0) \ne 01</tex>. Тогда существует единственный формальный степенной ряд вправо: <tex>BF(s) + s \cdot F(s) = (f_0 + f_1 s + f_2 s^2 + f_3 s^3 + \dots) + (0 + f_0 s + f_1 s^2 + f_2 s^3 + \dots) = (f_0 + 0) + (f_1 + f_0) s + (f_2 + f_1) s^2 + (f_3 + f_2) s^3 + \dots = b_0 f_1 + b_1 f_2 s + b_2 f_3 s^2 + b_3 f_4 s^3 + \dots </tex>. Заметим, такой что результат равен сдвигу <tex>AF(s)B(s) = </tex> на <tex>1</tex>влево.|proof = Составим и решим уравнение:Снова проведем доказательство по индукции. <tex>b_0 F(s) + s \cdot F(s) = \dfrac{F(s) - 1}{a_0s}</tex>. Пусть теперь все коэффициенты ряда ; <tex>B</tex> вплоть до степени <tex>n F(s)(s^2 + s - 1) = - 1</tex> однозначно определены. Коэффициент при ; <tex>F(s) = \dfrac{1}{1 - s - s^n2}</tex> определяется из условия <tex>a_0 b_n + a_1 b_. ==См. также==* [[Производящая функция]]* [[Производящие функции нескольких переменных]]* [[Разложение рациональной функции в ряд]] ==Источники информации==* ''Ландо С. К.'', Лекции о производящих функциях. {{n - 1--}} + \dots + a_n b_0 = 0</tex>3-е изд. Это линейное уравнение на <tex>b_n</tex>, причем коэффициент <tex>a_0</tex> при <tex>b_n</tex> отличен от нуляиспр. {{---}} М. Поэтому уравнение имеет единсвтенное решение: МЦНМО, 2007.{{---}}144с. ISBN 978-5-94057-042-4 [[Категория: Дискретная математика и алгоритмы]][[Категория: Комбинаторика]]