40
правок
Изменения
Произведение Адамара, Начало
}}
Таким образом, произведение Адамара двух последовательностей {{---}} это последовательность, состоящая из почленных произведений соответственных членов этих последовательностей. Необходимость в производящей функции для произведения Адамара уже встречалась: в задаче о числе счастливых билетов нам понадобилось вычислить сумму квадратов коэффициентов производящего многочлена <tex>A_3</tex>. Эта необходимость возникает при перечислении пар объектов одинакового порядка: если число объектов первого типа равно <tex>a_n</tex>, а число объектов второго типа <tex>b_n</tex> то число пар объектов, составленных из элементов первого и второго типа, равно <tex>a_n b_n</tex>.
==Теорема==
{{Теорема
|statement= Произведение Адамара двух рациональных производящих функций рационально.}}
Для доказательства этой теоремы нам понадобится новая характеризация рациональных производящих функций.
{{Лемма
|statement= Производящая функция для последовательности <tex>a_0, a_1,
a_2, \dots</tex> рациональна тогда и только тогда, когда существуют такие числа <tex>q_1, \dots, q_l</tex> и такие многочлены <tex>p_1(n),
\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>
Выражение в правой части равенства называется квазимногочленом от переменной <tex>n</tex>.}}
===Доказательство===
Заметим прежде всего, что производящая функция <tex>(1 - q s)^{-k}</tex> имеет вид
<tex>(1 - q s)^{-k} = 1 - {-k \choose 1} q s + {-k \choose 2} q^{2} s^{2} -
{-k\choose 3} q^{3} s^{3} + \dots =
= 1+ {k \choose 1} q s + {k + 1 \choose 2} q^{2} s^{2} + {k + 2 \choose 3}
q^{3} s^{3} + \dots =
= 1 + {k \choose k - 1} q s + {k + 1 \choose k - 1} q^{2} s^{2} + {k + 2 \choose k - 1} q^{3} s^{3} + \dots</tex>
Коэффициент при <tex>s^n</tex> в этой производящей функции равен
