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

Лемма о квазимногочленах

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

Определение:

Произведением Адамара (англ. 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]\triangleright[/math]

[math]\Rightarrow[/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] в этой производящей функции равен [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]f_n = p_1(n) p_1^n+\dots+p_l(n) p_l^n[/math],

Где обратные корни, [math]p_i \in \mathbb{C}[/math], являются константами и где [math]p_i(n)[/math] это многочлен от [math]n[/math] для всех [math]1 \leqslant i \leqslant l[/math]. Для примера произведение Адамара двух производящих функций:

[math]F(z) = \dfrac{1}{1 + a_1 z + a_2 z^2}[/math]

и

[math]G(z) = \dfrac{1}{1 + b_1 z + b_2 z^2}[/math]

Задаются формулами рациональных производящих функций, тогда их произведением Адамара, тоже будет рациональная производящая функция

[math](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}[/math]

См. также

• Производящая функция
• Задача о счастливых билетах

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

• Ландо С. К., Лекции о производящих функциях. — 3-е изд., испр. — М.: МЦНМО, 2007. — 26с. ISBN 978-5-94057-042-4
• Wikipedia — Generating function transformation