Изменения

==Деление=={{Определение|id = div|definition=''Суммой'Обратным по умножению' '' (англ. ''multiplicative inverse'') к формальному степенному ряду <tex>A(s)</tex> и называется такой ряд <tex>B(s)</tex> называется ряд , что <tex>A(s) + B(s) = 1</tex>. Обозначение: <tex>B(a_0 + b_0s) + = A^{-1}(a_1 + b_1) s + (a_2 + b_2) s^2 + \dots</tex>.}}

''Произведением'' {{Лемма|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 + a_2 b_0) s^2 + \dots</tex>.Заметим, что условие <tex>A(s)B(s) = 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^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(s) B(s)^{-1}</tex> (при условии существования у <tex>B(s)</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(t) = -t</tex>, то <tex>A(B(t)) = A(-t) = a_0 -a_1 t + a_2 t^2 - a_3 t^3 + \dots</tex>.

Если, напримерОперация подстановки в случае, когда <tex>B(t0) = -t\ne 0</tex>, то <tex>A(Bне определена. (tПри попытке подставить такой ряд для вычисления коэффициентов результата возникает необходимость суммирования бесконечных числовых рядов)) = A(-t) = a_0 -a_1 t + a_2 t^2 - a_3 t^3 + \dots</tex>.

Операция ==Обратный ряд=={{Определение|definition='''Левым обратным''' (англ. ''left inverse'') по операции подстановки в случаеформальным степенным рядом для ряда <tex>B(t)</tex> называется такой ряд <tex>A(s)</tex>, когда что <tex>A(B(0t)) \ne 0= t</tex>. Аналогично, не определена'''правым обратным''' (англ. ''right inverse'') формальным степенным рядом для <tex>B(При попытке подставить t)</tex> называется такой ряд возникает необходимость суммирования бесконечных числовых рядов<tex>C(u)</tex>, что <tex>B(C(u))= u</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>AB(s)</tex> и <tex>C</tex> единственны. Функция При этом, ряды <tex>A</tex> называется левой обратной, а функция и <tex>C</tex> {{---}} правой обратной к функции <tex>B</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>k</tex> получается домножением его на <tex>s^k</tex>. Например, пусть исходный ряд <tex>A(s) = Пусть a_0 + a_1 s + a_2 s^2 + \dots</tex>. Сдвинем его на <tex>k</tex> вправо: <tex>B(s) = s^k \cdot A(s) = a_0 s^k + a_1 s ^{k + 1} + a_2 s^{k + 2} + \dots = 0 + 0 s + 0 s^2 + a_3 \dots + a_0 s^k + a_1 s^3 {k + 1} + \dots </tex> {{---}} формальный степенной . ===Сдвиг влево===Сдвинуть рядвлево на <tex>k</tex> можно, причем вычтя из него первые <tex>A(0) \ne 0k</tex> слагаемых и затем разделив его на <tex>s^k</tex>. Тогда существует единственный формальный степенной Например, сдвинем ряд <tex>BA(s) = b_0 a_0 + b_1 a_1 s + b_2 a_2 s^2 + b_3 s^3 + \dots </tex>, такой что на <tex>k</tex> влево: <tex>B(s) = \dfrac{A(s)B- (a_0 + a_1 s + a_2 s^2 + \dots + a_{k - 1} s^{k - 1}) }{s^k} = a_k + a_{k + 1} s + a_{k + 2} s^2 + \dots</tex>.|proof = :Снова проведем доказательство по индукцииСдвиги могут быть полезны для упрощения вычисления производящих функций.Например, попробуем получить функцию для чисел Фибоначчи, используя сдвиги. Пусть формальный степенной ряд для нее равен <tex>b_0 F(s) = f_0 + f_1 s + f_2 s^2 + \dfrac{1}{a_0}dots</tex>. Пусть теперь все коэффициенты ряда , при этом <tex>Bf_0 = f_1 = 1</tex> вплоть до степени , <tex>f_n = f_{n - 2} + f_{n - 1}, n > 1</tex> однозначно определены. Коэффициент при Рассмотрим сумму этого ряда и ряда, полученного из него сдвигом на <tex>s^n1</tex> определяется из условия вправо: <tex>a_0 b_n F(s) + s \cdot F(s) = (f_0 + f_1 s + f_2 s^2 + a_1 b_{n - 1} f_3 s^3 + \dots ) + (0 + a_n b_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 = f_1 + f_2 s + f_3 s^2 + f_4 s^3 + \dots</tex>. Заметим, что результат равен сдвигу <tex>F(s)</tex>на <tex>1</tex> влево. Это линейное Составим и решим уравнение на : <tex>b_nF(s) + s \cdot F(s) = \dfrac{F(s) - 1}{s}</tex>, причем коэффициент ; <tex>a_0F(s)(s^2 + s - 1) = -1</tex> при ; <tex>b_nF(s) = \dfrac{1}{1 - s - s^2}</tex> отличен от нуля. Поэтому уравнение имеет единсвтенное решение ==См.также==* [[Производящая функция]]* [[Производящие функции нескольких переменных]]* [[Разложение рациональной функции в ряд]] ==Источники информации==* ''Ландо С. К.'', Лекции о производящих функциях. {{---}} 3-е изд., испр. {{---}} М.: МЦНМО, 2007. {{---}}144с. ISBN 978-5-94057-042-4 [[Категория: Дискретная математика и алгоритмы]][[Категория: Комбинаторика]]