693
правки
Изменения
→Рациональность произведения Адамара
Одно из наиболее привлекательных свойств рациональных [[Производящая функция|производящих функций ]] {{---}} их замкнутость относительно произведения Адамара.
{{Определение
|definition = '''Произведением Адамара''' (англ. ''Hadamard product'') производящих функций <tex>A(s) = a_0 + a_1 s + a_2 s^2 + \dots</tex> и <tex>B(s) = b_0 + b_1 s + b_2 s^2 + \dots</tex> называется производящая функция <tex>A(s) \circ B(s) = (a_0 b_0) + (a_1 b_1) s + (a_2 b_2) s^2 + \dots</tex>.
}}
Таким образом, произведение Адамара двух последовательностей {{---}} это последовательность, состоящая из почленных произведений соответственных членов этих последовательностей. Необходимость в производящей функции для произведения Адамара уже встречалась: в [[Задача о счастливых билетах|задаче о числе счастливых билетов]] нам понадобилось вычислить сумму квадратов коэффициентов производящего многочлена <tex>A_3</tex>. Эта необходимость возникает при перечислении пар объектов одинакового порядка: если число объектов первого типа равно <tex>a_n</tex>, а число объектов второго типа <tex>b_n</tex> то число пар объектов, составленных из элементов первого и второго типа, равно <tex>a_n b_n</tex>.
==Рациональность произведения Адамара==
{{Лемма
\dots, p_l(n)</tex>, что начиная с некоторого номера <tex>n</tex>
<tex>a_n = p_1(n) q_1^n + \dots + p_l(n) q_l^n.</tex>
Выражение в правой части равенства называется '''квазимногочленом ''' (англ. ''quasypolynomial'') от переменной <tex>n</tex>.
|proof=
Заметим прежде всего, что производящая функция <tex>(1 - q s)^{-k}</tex> имеет вид
<tex>(1 - q s)^{-k} = 1 - \begin{pmatrix} -k \choose \ 1\end{pmatrix} q s + \begin{pmatrix} -k \choose \ 2\end{pmatrix} q^{2} s^{2} - \begin{pmatrix} -k\choose \ 3\end{pmatrix} q^{3} s^{3} + \dots = </tex>:::<tex> = 1+ \begin{pmatrix} k \choose \ 1\end{pmatrix} q s + \begin{pmatrix} k + 1 \choose \ 2\end{pmatrix} q^{2} s^{2} + \begin{pmatrix} k + 2 \choose \ 3\end{pmatrix} q^{3} s^{3} + \dots =</tex>:::<tex> = 1 + \begin{pmatrix} k \choose \ k - 1\end{pmatrix} q s + \begin{pmatrix} k + 1 \choose \ k - 1\end{pmatrix} q^{2} s^{2} + \begin{pmatrix} k + 2 \choose \ k - 1\end{pmatrix} q^{3} s^{3} + \dots</tex>
Коэффициент при <tex>s^n</tex> в этой производящей функции равен
является тоже рациональной. Проще говоря, произведение Адамара двух рациональных производящих функций рационально.
|proof= Для доказательства теоремы осталось заменитьзаметить, что произведение квазимногочленов является квазимногочленом. Это утверждение непосредственно вытекает из формулы <tex>a_n = p_1(n) q_1^n + \dots + p_l(n) q_l^n.</tex>}} =====Пример произведения Адамара рациональных производящих функций===== В целом, Произведение Адамара двух рациональных производящих функций тоже рационально. Это видно, заметив, что коэффициенты рациональной производящей функции образуют квазимногочлен вида<tex>f_n = p_1(n) p_1^n+\dots+p_l(n) p_l^n</tex>, Где взаимные корни, <tex>p_i \in \mathbb{C}</tex>, являются фиксированными скалярами и где <tex>p_i(n)</tex> это многочлен от <tex>n</tex> для всех <tex>1 \leqslant i \leqslant l</tex>. Для примера произведение Адамара двух производящих функций: <tex>F(z) = \dfrac{1}{1 + a_1 z + a_2 z^2}</tex> и <tex>G(z) = \dfrac{1}{1 + b_1 z + b_2 z^2}</tex> Задаются формулами рациональных производящих функций, тогда их произведением Адамара, тоже будет рациональная производящая функция <tex>(F \circ G)(z) = \dfrac{1 - a_2 b_2 z^2}{1 - a_1 b_1 z + (a_2 b_1^2 + a_1^2 b_2 - a_2 b_2) z^2 - a_1 a_2 b_1 b_2 z^3 + a_2^2 b_2^2 z^4}</tex>
== См. также ==
