Произведение Адамара рациональных производящих функций
Одно из наиболее привлекательных свойств рациональных производящих функций — их замкнутость относительно произведения Адамара.
Определение: |
Произведением Адамара (англ. Hadamard product) производящих функций | и называется производящая функция .
Таким образом, произведение Адамара двух последовательностей — это последовательность, состоящая из почленных произведений соответственных членов этих последовательностей. Необходимость в производящей функции для произведения Адамара уже встречалась: в задаче о числе счастливых билетов нам понадобилось вычислить сумму квадратов коэффициентов производящего многочлена . Эта необходимость возникает при перечислении пар объектов одинакового порядка: если число объектов первого типа равно , а число объектов второго типа то число пар объектов, составленных из элементов первого и второго типа, равно .
Содержание
Рациональность произведения Адамара
Лемма: |
Производящая функция для последовательности рациональна тогда и только тогда, когда существуют такие числа и такие многочлены , что начиная с некоторого номера
Выражение в правой части равенства называется квазимногочленом (англ. quasypolynomial) от переменной . |
Доказательство: |
Заметим прежде всего, что производящая функция имеет вид
Коэффициент при в этой производящей функции равен, где — многочлен от степени . Всякая рациональная функция от переменной представляется в виде линейной комбинации многочлена и элементарных дробей вида , поэтому коэффициенты соответствующей производящей функции являются квазимногочленами.
Наоборот, предположим, что коэффициенты производящей функции, начиная с некоторого номера, представляются в виде квазимногочлена. Покажем, что в случае квазимногочлена Для произвольного квазимногочлена мы получаем линейную комбинацию функций такого вида при разных соответствующая производящая функция рациональна. Пусть степень многочлена равна . Многочлены , определенные равенством , образуют базис в пространстве многочленов степени не выше . Действительно, любая последовательность многочленов степеней образует базис в этом пространстве. Поэтому многочлен представляется в виде линейной комбинации многочленов и соответствующая производящая функция есть просто линейная комбинация функций , . . |
Теорема: |
Предположим, что производящие функции для последовательностей и
и являются рациональными. Значит производящая функция для их произведения Адамара является тоже рациональной. Проще говоря, произведение Адамара двух рациональных производящих функций рационально. . |
Доказательство: |
Для доказательства теоремы осталось заметить, что произведение квазимногочленов является квазимногочленом. Это утверждение непосредственно вытекает из формулы | .
Примеры применения теоремы
Задача: |
Представьте в виде квазимногочлена коэффициент производящей функции |
Разобьем дробь на сумму простых дробей:
Воспользуемся результатом леммы: коэффициент при равен .
Для первой дроби
, для второй: .Тогда
Задача: |
Представьте в виде квазимногочлена коэффициент производящей функции |
Разобьем на сумму простых дробей:
Используем лемму:
первая дробь:
, вторая: , третья: , четвертая: ,тогда
См. также
Источники информации
- Ландо С. К., Лекции о производящих функциях. — 3-е изд., испр. — М.: МЦНМО, 2007. — 26с. ISBN 978-5-94057-042-4
- Wikipedia — Generating function transformation