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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Произведение Адамара, Начало)
(Произведение Адамара, Начало)
Строка 16: Строка 16:
 
===Доказательство===
 
===Доказательство===
 
Заметим прежде всего, что производящая функция <tex>(1 - q s)^{-k}</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} -
+
:<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 = </tex>
{-k\choose 3} q^{3} s^{3} + \dots =
+
::::<tex>= 1+ {k \choose 1} q s + {k + 1 \choose 2} q^{2} s^{2} + {k + 2 \choose 3} q^{3} s^{3} + \dots =</tex>
= 1+ {k \choose 1} q s + {k + 1 \choose 2} q^{2} s^{2} + {k + 2 \choose 3}
+
::::<tex>= 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>
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> в этой производящей функции равен
 
Коэффициент при <tex>s^n</tex> в этой производящей функции равен

Версия 17:46, 10 июня 2017

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

Определение:
Произведением Адамара (англ. 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]

Выражение в правой части равенства называется квазимногочленом от переменной [math]n[/math].

Доказательство

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

[math](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 = [/math]
[math]= 1+ {k \choose 1} q s + {k + 1 \choose 2} q^{2} s^{2} + {k + 2 \choose 3} q^{3} s^{3} + \dots =[/math]
[math]= 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[/math]

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