Произведение Адамара рациональных производящих функций — различия между версиями
(→Рациональность произведения Адамара) |
|||
(не показано 9 промежуточных версий 3 участников) | |||
Строка 1: | Строка 1: | ||
− | |||
Одно из наиболее привлекательных свойств рациональных [[Производящая функция|производящих функций]] {{---}} их замкнутость относительно произведения Адамара. | Одно из наиболее привлекательных свойств рациональных [[Производящая функция|производящих функций]] {{---}} их замкнутость относительно произведения Адамара. | ||
{{Определение | {{Определение | ||
Строка 5: | Строка 4: | ||
}} | }} | ||
Таким образом, произведение Адамара двух последовательностей {{---}} это последовательность, состоящая из почленных произведений соответственных членов этих последовательностей. Необходимость в производящей функции для произведения Адамара уже встречалась: в [[Задача о счастливых билетах|задаче о числе счастливых билетов]] нам понадобилось вычислить сумму квадратов коэффициентов производящего многочлена <tex>A_3</tex>. Эта необходимость возникает при перечислении пар объектов одинакового порядка: если число объектов первого типа равно <tex>a_n</tex>, а число объектов второго типа <tex>b_n</tex> то число пар объектов, составленных из элементов первого и второго типа, равно <tex>a_n b_n</tex>. | Таким образом, произведение Адамара двух последовательностей {{---}} это последовательность, состоящая из почленных произведений соответственных членов этих последовательностей. Необходимость в производящей функции для произведения Адамара уже встречалась: в [[Задача о счастливых билетах|задаче о числе счастливых билетов]] нам понадобилось вычислить сумму квадратов коэффициентов производящего многочлена <tex>A_3</tex>. Эта необходимость возникает при перечислении пар объектов одинакового порядка: если число объектов первого типа равно <tex>a_n</tex>, а число объектов второго типа <tex>b_n</tex> то число пар объектов, составленных из элементов первого и второго типа, равно <tex>a_n b_n</tex>. | ||
+ | |||
+ | ==Рациональность произведения Адамара== | ||
{{Лемма | {{Лемма | ||
Строка 11: | Строка 12: | ||
\dots, p_l(n)</tex>, что начиная с некоторого номера <tex>n</tex> | \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>a_n = p_1(n) q_1^n + \dots + p_l(n) q_l^n.</tex> | ||
− | Выражение в правой части равенства называется квазимногочленом от переменной <tex>n</tex>. | + | Выражение в правой части равенства называется '''квазимногочленом''' (англ. ''quasypolynomial'') от переменной <tex>n</tex>. |
|proof= | |proof= | ||
Строка 18: | Строка 19: | ||
Заметим прежде всего, что производящая функция <tex>(1 - q s)^{-k}</tex> имеет вид | Заметим прежде всего, что производящая функция <tex>(1 - q s)^{-k}</tex> имеет вид | ||
− | <tex>(1 - q s)^{-k} = 1 - {-k \ | + | <tex>(1 - q s)^{-k} = 1 - \begin{pmatrix} -k \\ 1 \end{pmatrix} q s + \begin{pmatrix} -k \\ 2 \end{pmatrix} q^{2} s^{2} - \begin{pmatrix} -k \\ 3 \end{pmatrix} q^{3} s^{3} + \dots = </tex> |
− | :::<tex> = 1+ {k \ | + | :::<tex> = 1+ \begin{pmatrix} k \\ 1 \end{pmatrix} q s + \begin{pmatrix} k+1 \\ 2 \end{pmatrix} q^{2} s^{2} + \begin{pmatrix} k+2 \\ 3 \end{pmatrix} q^{3} s^{3} + \dots =</tex> |
− | :::<tex> = 1 + {k \ | + | :::<tex> = 1 + \begin{pmatrix} k \\ k-1 \end{pmatrix} q s + \begin{pmatrix} k+1 \\ k-1 \end{pmatrix} q^{2} s^{2} + \begin{pmatrix} k+2 \\ k-1 \end{pmatrix}q^{3} s^{3} + \dots</tex> |
Коэффициент при <tex>s^n</tex> в этой производящей функции равен | Коэффициент при <tex>s^n</tex> в этой производящей функции равен | ||
Строка 32: | Строка 33: | ||
Наоборот, предположим, что коэффициенты производящей функции, начиная с некоторого номера, представляются в виде квазимногочлена. Покажем, что в случае квазимногочлена <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>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>.}} | Для произвольного квазимногочлена мы получаем линейную комбинацию функций такого вида при разных <tex>q_i</tex>.}} | ||
− | |||
− | |||
{{Теорема | {{Теорема | ||
Строка 46: | Строка 45: | ||
является тоже рациональной. Проще говоря, произведение Адамара двух рациональных производящих функций рационально. | является тоже рациональной. Проще говоря, произведение Адамара двух рациональных производящих функций рационально. | ||
− | |proof= Для доказательства теоремы осталось | + | |proof= Для доказательства теоремы осталось заметить, что произведение квазимногочленов является квазимногочленом. Это утверждение непосредственно вытекает из формулы <tex>a_n = p_1(n) q_1^n + \dots + p_l(n) q_l^n</tex>.}} |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
== См. также == | == См. также == |
Версия 19:20, 1 марта 2018
Одно из наиболее привлекательных свойств рациональных производящих функций — их замкнутость относительно произведения Адамара.
Определение: |
Произведением Адамара (англ. Hadamard product) производящих функций | и называется производящая функция .
Таким образом, произведение Адамара двух последовательностей — это последовательность, состоящая из почленных произведений соответственных членов этих последовательностей. Необходимость в производящей функции для произведения Адамара уже встречалась: в задаче о числе счастливых билетов нам понадобилось вычислить сумму квадратов коэффициентов производящего многочлена . Эта необходимость возникает при перечислении пар объектов одинакового порядка: если число объектов первого типа равно , а число объектов второго типа то число пар объектов, составленных из элементов первого и второго типа, равно .
Рациональность произведения Адамара
Лемма: |
Производящая функция для последовательности рациональна тогда и только тогда, когда существуют такие числа и такие многочлены , что начиная с некоторого номера
Выражение в правой части равенства называется квазимногочленом (англ. quasypolynomial) от переменной . |
Доказательство: |
Заметим прежде всего, что производящая функция имеет вид
Коэффициент при в этой производящей функции равен, где — многочлен от степени . Всякая рациональная функция от переменной представляется в виде линейной комбинации многочлена и элементарных дробей вида , поэтому коэффициенты соответствующей производящей функции являются квазимногочленами.
Наоборот, предположим, что коэффициенты производящей функции, начиная с некоторого номера, представляются в виде квазимногочлена. Покажем, что в случае квазимногочлена Для произвольного квазимногочлена мы получаем линейную комбинацию функций такого вида при разных соответствующая производящая функция рациональна. Пусть степень многочлена равна . Многочлены , определенные равенством , образуют базис в пространстве многочленов степени не выше . Действительно, любая последовательность многочленов степеней образует базис в этом пространстве. Поэтому многочлен представляется в виде линейной комбинации многочленов и соответствующая производящая функция есть просто линейная комбинация функций , . . |
Теорема: |
Предположим, что производящие функции для последовательностей и
и являются рациональными. Значит производящая функция для их произведения Адамара является тоже рациональной. Проще говоря, произведение Адамара двух рациональных производящих функций рационально. . |
Доказательство: |
Для доказательства теоремы осталось заметить, что произведение квазимногочленов является квазимногочленом. Это утверждение непосредственно вытекает из формулы | .
См. также
Источники информации
- Ландо С. К., Лекции о производящих функциях. — 3-е изд., испр. — М.: МЦНМО, 2007. — 26с. ISBN 978-5-94057-042-4
- Wikipedia — Generating function transformation