Произведение Адамара рациональных производящих функций — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Перевод строки в примере)
м (Описание задач исправлено)
Строка 50: Строка 50:
 
== Примеры применения теоремы ==
 
== Примеры применения теоремы ==
 
{{Задача
 
{{Задача
−
|definition = Представьте в виде линейной рекуррентности производящую функцию <tex>A(s)=\dfrac{1 + 2s}{(1 - 2s)(1 + 3s)}</tex>
+
|definition = Представьте в виде квазимногочлена коэффициент производящей функции <tex>A(s)=\dfrac{1 + 2s}{(1 - 2s)(1 + 3s)}</tex>
 
}}
 
}}
 
Разобьем дробь на сумму простых дробей: <tex>A(s)=\dfrac{1 + 2s}{(1 - 2s)(1 + 3s)}=\dfrac{1/5}{1 + 3s} + \dfrac{4/5}{1 - 2s}</tex>
 
Разобьем дробь на сумму простых дробей: <tex>A(s)=\dfrac{1 + 2s}{(1 - 2s)(1 + 3s)}=\dfrac{1/5}{1 + 3s} + \dfrac{4/5}{1 - 2s}</tex>
Строка 58: Строка 58:
 
Для первой дроби <tex>k = 1,\, q = -3</tex>, для второй: <tex>k = 1,\, q = 2</tex>.
 
Для первой дроби <tex>k = 1,\, q = -3</tex>, для второй: <tex>k = 1,\, q = 2</tex>.
  
−
Тогда <tex>a_{n} = \frac{1}{5} \cdot \dfrac{1}{(1 - 1)!} (-3)^{n} + \frac{4}{5} \cdot \dfrac{1}{(1 - 1)!} (2)^{n} =
+
Тогда <tex>a_{n} = \dfrac{1}{5} \cdot \dfrac{1}{(1 - 1)!} (-3)^{n} + \dfrac{4}{5} \cdot \dfrac{1}{(1 - 1)!} (2)^{n} =
−
\frac{(-3)^{n}}{5} + \frac{4}{5} \cdot 2^{n} </tex>
+
\dfrac{(-3)^{n}}{5} + \dfrac{4}{5} \cdot 2^{n} </tex>
  
 
{{Задача
 
{{Задача
−
|definition = Представьте в виде линейной рекуррентности производящую функцию <tex>A(s)=\dfrac{s^2}{(1 - 2s)^{2}(1 + s)(1 - s)}</tex>
+
|definition = Представьте в виде квазимногочлена коэффициент производящей функции <tex>A(s)=\dfrac{s^2}{(1 - 2s)^{2}(1 + s)(1 - s)}</tex>
 
}}
 
}}
 
Разобьем на сумму простых дробей: <tex>A(s)=\dfrac{s^2}{(1 - 2s)^{2}(1 + s)(1 - s)} = \dfrac{1/18}{1 + s} + \dfrac{-8/9}{1 - 2s} + \dfrac{1/3}{(1 - 2s)^2} + \dfrac{1/2}{1 - s}</tex>
 
Разобьем на сумму простых дробей: <tex>A(s)=\dfrac{s^2}{(1 - 2s)^{2}(1 + s)(1 - s)} = \dfrac{1/18}{1 + s} + \dfrac{-8/9}{1 - 2s} + \dfrac{1/3}{(1 - 2s)^2} + \dfrac{1/2}{1 - s}</tex>
Строка 70: Строка 70:
 
первая дробь: <tex>k = 1,\, q = -1</tex>, вторая: <tex>k = 1, q = 2</tex>, третья: <tex>k = 2,\, q = 2</tex>, четвертая: <tex>k = 1,\, q = 1</tex>,
 
первая дробь: <tex>k = 1,\, q = -1</tex>, вторая: <tex>k = 1, q = 2</tex>, третья: <tex>k = 2,\, q = 2</tex>, четвертая: <tex>k = 1,\, q = 1</tex>,
  
−
тогда <tex>a_{n} = \dfrac{(-1)^n}{18} - \dfrac{8}{9} \cdot 2^n + \dfrac{n + 1}{(2 - 1)!} \cdot 2^n + \dfrac{(1)^n}{2}=(n + \frac{1}{9}) \cdot 2^n + (-1)^{n}\frac{1}{18} + \frac{1}{2}</tex>
+
тогда <tex>a_{n} = \dfrac{(-1)^n}{18} - \dfrac{8}{9} \cdot 2^n + \dfrac{n + 1}{(2 - 1)!} \cdot 2^n + \dfrac{1}{2}\cdot 1^n = \left(n + \dfrac{1}{9}\right) \cdot 2^n + (-1)^{n}\dfrac{1}{18} + \dfrac{1}{2}</tex>
  
 
== См. также ==
 
== См. также ==

Версия 16:24, 9 июня 2021

Одно из наиболее привлекательных свойств рациональных производящих функций — их замкнутость относительно произведения Адамара.

Определение:
Произведением Адамара (англ. Hadamard product) производящих функций [math]A(s) = a_0 + a_1 s + a_2 s^2 + \dots[/math] и [math]B(s) = b_0 + b_1 s + b_2 s^2 + \dots[/math] называется производящая функция [math]A(s) \circ B(s) = (a_0 b_0) + (a_1 b_1) s + (a_2 b_2) s^2 + \dots[/math].

Таким образом, произведение Адамара двух последовательностей — это последовательность, состоящая из почленных произведений соответственных членов этих последовательностей. Необходимость в производящей функции для произведения Адамара уже встречалась: в задаче о числе счастливых билетов нам понадобилось вычислить сумму квадратов коэффициентов производящего многочлена [math]A_3[/math]. Эта необходимость возникает при перечислении пар объектов одинакового порядка: если число объектов первого типа равно [math]a_n[/math], а число объектов второго типа [math]b_n[/math] то число пар объектов, составленных из элементов первого и второго типа, равно [math]a_n b_n[/math].

Рациональность произведения Адамара

Лемма:
Производящая функция для последовательности [math]a_0, a_1, a_2, \dots[/math] рациональна тогда и только тогда, когда существуют такие числа [math]q_1, \dots, q_l[/math] и такие многочлены [math]p_1(n), \dots, p_l(n)[/math], что начиная с некоторого номера [math]n[/math]

[math]a_n = p_1(n) q_1^n + \dots + p_l(n) q_l^n.[/math]

Выражение в правой части равенства называется квазимногочленом (англ. quasypolynomial) от переменной [math]n[/math].
Доказательство:
[math]\triangleright[/math]

[math]\Rightarrow[/math]

Заметим прежде всего, что производящая функция [math](1 - q s)^{-k}[/math] имеет вид

[math](1 - q s)^{-k} = 1 - \begin{pmatrix} -k \\ 1 \end{pmatrix} q s + \begin{pmatrix} -k \\ 2 \end{pmatrix} q^{2} s^{2} - \begin{pmatrix} -k \\ 3 \end{pmatrix} q^{3} s^{3} + \dots = [/math]

[math] = 1+ \begin{pmatrix} k \\ 1 \end{pmatrix} q s + \begin{pmatrix} k+1 \\ 2 \end{pmatrix} q^{2} s^{2} + \begin{pmatrix} k+2 \\ 3 \end{pmatrix} q^{3} s^{3} + \dots =[/math]
[math] = 1 + \begin{pmatrix} k \\ k-1 \end{pmatrix} q s + \begin{pmatrix} k+1 \\ k-1 \end{pmatrix} q^{2} s^{2} + \begin{pmatrix} k+2 \\ k-1 \end{pmatrix}q^{3} s^{3} + \dots[/math]

Коэффициент при [math]s^n[/math] в этой производящей функции равен

[math]\dfrac{(n + 1)(n + 2)\dots(n + k - 1)}{(k - 1)!} q^{n} = P_{k - 1}(n) q^{n}[/math],

где [math]P_{k - 1}(n)[/math] — многочлен от [math]n[/math] степени [math]k - 1[/math]. Всякая рациональная функция от переменной [math]s[/math] представляется в виде линейной комбинации многочлена и элементарных дробей вида [math](1 - q_i s)^{-k_i}[/math], поэтому коэффициенты соответствующей производящей функции являются квазимногочленами.

[math]\Leftarrow[/math]

Наоборот, предположим, что коэффициенты производящей функции, начиная с некоторого номера, представляются в виде квазимногочлена. Покажем, что в случае квазимногочлена [math]p(n) q^{n}[/math] соответствующая производящая функция рациональна. Пусть степень многочлена [math]p[/math] равна [math]k - 1[/math]. Многочлены [math]P_0, P_1, \dots, P_{k - 1}[/math], определенные равенством [math]\dfrac{(n + 1)(n + 2)\dots(n + k - 1)}{(k - 1)!} q^{n} = P_{k - 1}(n) q^{n}[/math], образуют базис в пространстве многочленов степени не выше [math] k - 1[/math]. Действительно, любая последовательность многочленов степеней [math]0, 1, \dots, k - 1[/math] образует базис в этом пространстве. Поэтому многочлен [math]p[/math] представляется в виде линейной комбинации многочленов [math]P_i[/math] и соответствующая производящая функция есть просто линейная комбинация функций [math](1 - q s)^{-j}[/math], [math]j = 0, 1, \dots, k - 1[/math].

Для произвольного квазимногочлена мы получаем линейную комбинацию функций такого вида при разных [math]q_i[/math].
[math]\triangleleft[/math]
Теорема:
Предположим, что производящие функции для последовательностей [math]a_0, a_1, a_2, \dots[/math] и [math]b_0, b_1, b_2, \dots[/math]

[math]A(s) = a_0 + a_1 s + a_2 s^2 + \dots[/math] и [math]B(s) = b_0 + b_1 s + b_2 s^2 + \dots[/math]

являются рациональными. Значит производящая функция для их произведения Адамара

[math]A(s) \circ B(s) = (a_0 b_0) + (a_1 b_1) s + (a_2 b_2) s^2 + \dots[/math].

является тоже рациональной. Проще говоря, произведение Адамара двух рациональных производящих функций рационально.
Доказательство:
[math]\triangleright[/math]
Для доказательства теоремы осталось заметить, что произведение квазимногочленов является квазимногочленом. Это утверждение непосредственно вытекает из формулы [math]a_n = p_1(n) q_1^n + \dots + p_l(n) q_l^n[/math].
[math]\triangleleft[/math]

Примеры применения теоремы

Задача:
Представьте в виде квазимногочлена коэффициент производящей функции [math]A(s)=\dfrac{1 + 2s}{(1 - 2s)(1 + 3s)}[/math]

Разобьем дробь на сумму простых дробей: [math]A(s)=\dfrac{1 + 2s}{(1 - 2s)(1 + 3s)}=\dfrac{1/5}{1 + 3s} + \dfrac{4/5}{1 - 2s}[/math]

Воспользуемся результатом леммы: коэффициент при [math]s^n[/math] равен [math]\dfrac{(n + 1)(n + 2)\dots(n + k - 1)}{(k - 1)!} q^{n}[/math].

Для первой дроби [math]k = 1,\, q = -3[/math], для второй: [math]k = 1,\, q = 2[/math].

Тогда [math]a_{n} = \dfrac{1}{5} \cdot \dfrac{1}{(1 - 1)!} (-3)^{n} + \dfrac{4}{5} \cdot \dfrac{1}{(1 - 1)!} (2)^{n} = \dfrac{(-3)^{n}}{5} + \dfrac{4}{5} \cdot 2^{n} [/math]


Задача:
Представьте в виде квазимногочлена коэффициент производящей функции [math]A(s)=\dfrac{s^2}{(1 - 2s)^{2}(1 + s)(1 - s)}[/math]

Разобьем на сумму простых дробей: [math]A(s)=\dfrac{s^2}{(1 - 2s)^{2}(1 + s)(1 - s)} = \dfrac{1/18}{1 + s} + \dfrac{-8/9}{1 - 2s} + \dfrac{1/3}{(1 - 2s)^2} + \dfrac{1/2}{1 - s}[/math]

Используем лемму:

первая дробь: [math]k = 1,\, q = -1[/math], вторая: [math]k = 1, q = 2[/math], третья: [math]k = 2,\, q = 2[/math], четвертая: [math]k = 1,\, q = 1[/math],

тогда [math]a_{n} = \dfrac{(-1)^n}{18} - \dfrac{8}{9} \cdot 2^n + \dfrac{n + 1}{(2 - 1)!} \cdot 2^n + \dfrac{1}{2}\cdot 1^n = \left(n + \dfrac{1}{9}\right) \cdot 2^n + (-1)^{n}\dfrac{1}{18} + \dfrac{1}{2}[/math]

См. также

Источники информации

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Произведение_Адамара_рациональных_производящих_функций&oldid=80973»