3.2. Производящие функции
Если имеется последовательность
то производящую функцию, соответствующую этой последовательности, можно определить как формальный степенной ряд
А могут быть рациональными числами или элементами любого поля.
Две производящие функции
и
называются равными, если
для всех
При более слабом допущении, что
для
, мы говорим, что
Сумма или разность двух производящих функций определяется равенством
а произведение задается формулой
Будем говорить, что
тогда и только тогда, когда
Отношение двух производящих функций, если оно существует, всегда единственно, так как если
то
и, как мы предлагаем проверить читателю, либо
либо
Если
то
при любом
и уравнение
не разрешимо относительно
Однако если
то
и
Следовательно,
Таким образом, производящая функция
имеет мультипликативную обратную тогда и только тогда, когда
Назовем
четной производящей функцией, если
для всех нечетных
и нечетной производящей функцией, если
для всех четных
Сумма или разность двух четных производящих функций дают четную функцию, а сумма или разность двух нечетных производящих функций — нечетную функцию.
Произведение двух четных или двух нечетных производящих функций — четная функция, произведение четной функции на нечетную — нечетная функция. Мультипликативно обратная к четной производящей функции (если она существует) — четная функция. Произвольная производящая функция мэжэт быть записана как сумма четной и нечетной производящах функций:
Мы используем значки - и для обозначения соответственно четной а нечетной функций. Отметим графическое сходство этих знаков с четной косинусоидальной и нечетной синусоидальной функциями
Важно подчеркнуть, что перечисленные свойства производящих функций никак не зависят от сходимости или расходимости ряда
при некоторых значениях
Например, при
этот ряд
расходится для всех ненулевых комплексных значений
Далее, коэффициенты
не обязательно должны быть действительными или комплексными числами. Производящее функции можно строить над любым полем.
Для заданной производящей функции
можно определить ее формальную производную
Если
то
С помощью индукции этот результат может быть распространен до известной формулы производной произведения нескольких производящих функций.
3.21. Теорема.
3.22. Следствие.
Таким образом, для формальной производной выполняются свойства обычной производной. Единственное отличие состоит в том, что формальная производная не связана с операцией предельного перехода.
Формальная производная применима также к производящим функциям, которые являются обычными многочленами. Это позволяет сформулировать следующий результат.
3.23. Теорема. Неприводимый многочлен
с ненулевой производной
является делителем многочлена
кратности
тогда и только тогда, когда
делит
Доказательство. Пусть
неприводимый делитель
так что
Тогда
Если многочлен
делит
то он также делит
и поэтому
не может делить
Значит,
делит
Таким образом,
является делителем
кратности
тогда и только тогда, когда он делит
т. е. тогда и только тогда, когда
делит н. о. д.
.
Эта теорема справедлива для всех полей. Пусть, например,
двоичный многочлен
Тогда
При этом разложение
на неприводимые множители имеет вид