1632
правки
Изменения
м
===Лемма о квазимногочленах ===
===Теорема о рациональности произведения Адамара===
В целом, Произведение Адамара двух рациональных производящих функций тоже рационально. Заметим это из того, что коэффициенты рациональной производящей функции образуют квазимногочлен видаВоспользуемся результатом [[#lemma1|леммы]]: коэффициент при <tex>s^n</tex> равен <tex>f_n = p_1\dfrac{(n+ 1) p_1^(n+2)\dots(n +p_lk - 1)}{(nk - 1) p_l!} q^{n}</tex>,.
Где обратные корни, Для первой дроби <tex>p_i k = 1,\in \mathbb{C}, q = -3</tex>, являются константами и где <tex>p_i(n)</tex> это многочлен от <tex>n</tex> для всех второй: <tex>k = 1 ,\leqslant i \leqslant l, q = 2</tex>. Для примера произведение Адамара двух производящих функций:
и{{Задача|definition = Представьте в виде квазимногочлена коэффициент производящей функции <tex>A(s)=\dfrac{s^2}{(1 - 2s)^{2}(1 + s)(1 - s)}</tex>.}}Разобьем на сумму простых дробей: <tex>GA(zs) = \dfrac{s^2}{(1- 2s)^{2}(1 + s)(1 - s)} = \dfrac{1 /18}{1 + s} + b_1 z \dfrac{-8/9}{1 - 2s} + b_2 z\dfrac{1/3}{(1 - 2s)^2} + \dfrac{1/2}{1 - s}</tex>.
Задаются формулами рациональных производящих функцийПервая дробь: <tex>k = 1, тогда их произведением Адамара\, тоже будет рациональная производящая функцияq = -1</tex>, вторая: <tex>k = 1,\, q = 2</tex>, третья: <tex>k = 2,\, q = 2</tex>, четвертая: <tex>k = 1,\, q = 1</tex>.
rollbackEdits.php mass rollback
Одно из наиболее привлекательных свойств рациональных [[Производящая функция|производящих функций]] {{---}} их замкнутость относительно произведения Адамара.
{{Определение
}}
Таким образом, произведение Адамара двух последовательностей {{---}} это последовательность, состоящая из почленных произведений соответственных членов этих последовательностей. Необходимость в производящей функции для произведения Адамара уже встречалась: в [[Задача о счастливых билетах|задаче о числе счастливых билетов]] нам понадобилось вычислить сумму квадратов коэффициентов производящего многочлена <tex>A_3</tex>. Эта необходимость возникает при перечислении пар объектов одинакового порядка: если число объектов первого типа равно <tex>a_n</tex>, а число объектов второго типа <tex>b_n</tex> то число пар объектов, составленных из элементов первого и второго типа, равно <tex>a_n b_n</tex>.
==Рациональность произведения Адамара==
{{Лемма
|id=lemma1
|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>(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>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>.}}
{{Теорема
является тоже рациональной. Проще говоря, произведение Адамара двух рациональных производящих функций рационально.
|proof= Для доказательства теоремы осталось заменитьзаметить, что произведение квазимногочленов является квазимногочленом. Это утверждение непосредственно вытекает из формулы <tex>a_n = p_1(n) q_1^n + \dots + p_l(n) q_l^n.</tex>.}}
==Примеры применения теоремы ==Пример произведения Адамара рациональных производящих функций с использованием теоремы о рациональности их произведения{{Задача|definition =Представьте в виде квазимногочлена коэффициент производящей функции <tex>A(s)=\dfrac{1 + 2s}{(1 - 2s)(1 + 3s)}</tex>.}}Разобьем дробь на сумму простых дробей: <tex>A(s)=\dfrac{1 + 2s}{(1 - 2s)(1 + 3s)}=\dfrac{1/5}{1 + 3s} + \dfrac{4/5}{1 - 2s}</tex>.
Тогда <tex>Fa_{n} = \dfrac{1}{5} \cdot \dfrac{1}{(z1 - 1) = !} (-3)^{n} + \dfrac{4}{5} \cdot \dfrac{1}{(1 - 1)!} (2)^{n} =\dfrac{(-3)^{n}}{5} + a_1 z + a_2 z\dfrac{4}{5} \cdot 2^2{n}</tex>.
Тогда, используя лемму, получаем, что <tex>(F \circ G)(z) a_{n} = \dfrac{(-1 - a_2 b_2 z)^2n}{1 18} - a_1 b_1 z \dfrac{8}{9} \cdot 2^n + \dfrac{n + 1}{(a_2 b_1^2 + a_1^2 b_2 - a_2 b_21) z!} \cdot 2^n + \dfrac{1}{2 - a_1 a_2 b_1 b_2 z}\cdot 1^3 n = \left(n + a_2\dfrac{1}{9}\right) \cdot 2^2 b_2n + (-1)^{n}\dfrac{1}{18} + \dfrac{1}{2 z^4}</tex>.
== См. также ==
