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>. ==ТеоремаРациональность произведения Адамара=={{Теорема|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>
Выражение в правой части равенства называется '''квазимногочленом ''' (англ. ''quasypolynomial'') от переменной <tex>n</tex>.}}|proof===Доказательство=== <tex>\Rightarrow</tex>
Заметим прежде всего, что производящая функция <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> в этой производящей функции равен
<tex>\dfrac{(n + 1)(n + 2)\dots(n + k - 1)}{(k - 1)!} q^{n} = P_{k - 1}(n) q^{n}</tex>,
где <tex>P_{k - 1}(n)</tex> {{---}} многочлен от <tex>n</tex> степени <tex>k - 1</tex>. Всякая рациональная функция от переменной <tex>s</tex> представляется в виде линейной комбинации многочлена и элементарных дробей вида <tex>(1 - q_i s)^{-k_i}</tex>, поэтому коэффициенты соответствующей производящей функции являются квазимногочленами.
<tex>\Leftarrow</tex>
Наоборот, предположим, что коэффициенты производящей функции, начиная с некоторого номера, представляются в виде квазимногочлена. Покажем, что в случае квазимногочлена <tex>p(n) q^{n}</tex> соответствующая производящая функция рациональна. Пусть степень многочлена <tex>p</tex> равна <tex>k - 1</tex>. Многочлены <tex>P_0, P_1, \dots, P_{k - 1}</tex>, определенные равенством <tex>\dfrac{(n + 1)(n + 2)\dots(n + k - 1)}{(k - 1)!} q^{n} = P_{k - 1}(n) q^{n}</tex>, образуют базис в пространстве многочленов степени не выше <tex> k - 1</tex>. Действительно, любая последовательность многочленов степеней <tex>0, 1, \dots, k - 1</tex> образует базис в этом пространстве. Поэтому многочлен <tex>p</tex> представляется в виде линейной комбинации многочленов <tex>P_i</tex> и соответствующая производящая функция есть просто линейная комбинация функций <tex>(1 - q s)^{-j}</tex>, <tex>j = 0, 1, \dots, k - 1</tex>.
Для произвольного квазимногочлена мы получаем линейную комбинацию функций такого вида при разных <tex>q_i</tex>.}}
{{Теорема
|statement= Предположим, что производящие функции для последовательностей <tex>a_0, a_1, a_2, \dots</tex> и <tex>b_0, b_1, b_2, \dots</tex>
<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>.
является тоже рациональной. Проще говоря, произведение Адамара двух рациональных производящих функций рационально.
|proof= Для доказательства теоремы осталось заметить, что произведение квазимногочленов является квазимногочленом. Это утверждение непосредственно вытекает из формулы <tex>a_n = p_1(n) q_1^n + \dots + p_l(n) q_l^n</tex>.}}
== См. также ==
* [[Производящая функция]]
* [[Задача о счастливых билетах]]
==Источники информации==
* ''Ландо С. К.'', Лекции о производящих функциях. {{---}} 3-е изд., испр. {{---}} М.: МЦНМО, 2007. {{---}} 26с. ISBN 978-5-94057-042-4
* [[wikipedia:en:Generating function transformation | Wikipedia {{---}} Generating function transformation]]
[[Категория: Дискретная математика и алгоритмы]]
