Формальные степенные ряды и генерирующие функции

Введение

Формальные степенные ряды; коэффициенты кодируют информацию о последовательности, индексированной натуральными числами, генерирующие функции в математике.

В математике генерирующая функция представляет собой представление бесконечной последовательности чисел в виде коэффициентов формального степенного ряда. В отличие от обычного ряда, формальный степенной ряд не обязательно должен сходиться: фактически, генерирующая функция не рассматривается как функция, а "переменная" остается неопределённой. Генерирующие функции впервые были введены Авраамом де Муавром в 1730 году для решения общей линейной задачи рекуррентного соотношения. Можно обобщить на формальные степенные ряды от нескольких неопределённых, чтобы кодировать информацию о бесконечномерных многомерных массивах чисел. Существуют различные типы генерирующих функций, включая обыкновенные генерирующие функции, экспоненциальные генерирующие функции, ряды Ламбера, ряды Белла и ряды Дирихле; определения и примеры приведены ниже. В принципе, любая последовательность имеет генерирующую функцию каждого типа (за исключением того, что ряды Ламбера и Дирихле требуют, чтобы индексы начинались с 1, а не с 0), но простота их обработки может существенно различаться. Конкретная генерирующая функция, если таковая имеется, наиболее полезная в данном контексте, будет зависеть от природы последовательности и деталей рассматриваемой задачи. Генерирующие функции часто выражаются в замкнутой форме (а не в виде ряда) с помощью выражения, включающего операции, определённые для формальных рядов. Эти выражения относительно неопределённой x могут включать арифметические операции, дифференцирование по x и композицию с (то есть подстановку в) другие генерирующие функции; поскольку эти операции также определены для функций, результат выглядит как функция от x. Действительно, выражение в замкнутой форме часто можно интерпретировать как функцию, которую можно вычислить при (достаточно малых) конкретных значениях x, и которая имеет формальный ряд в качестве своего разложения в ряд; это объясняет обозначение "генерирующие функции". Однако такая интерпретация не обязательна, поскольку формальные ряды не обязаны давать сходящийся ряд при подстановке ненулевого числового значения вместо x. Кроме того, не все выражения, имеющие смысл как функции от x, имеют смысл как выражения, обозначающие формальные ряды; например, отрицательные и дробные степени x являются примерами функций, не имеющих соответствующего формального степенного ряда. Генерирующие функции не являются функциями в формальном смысле отображения из области определения в область значений. Генерирующие функции иногда называют генерирующими рядами, поскольку ряд членов можно назвать генератором последовательности коэффициентов.

In mathematics, a generating function is a representation of an infinite sequence of numbers as the coefficients of a formal power series. Unlike an ordinary series, the formal power series is not required to converge: in fact, the generating function is not actually regarded as a function, and the "variable" remains an indeterminate. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general linear recurrence problem. One can generalize to formal power series in more than one indeterminate, to encode information about infinite multi dimensional arrays of numbers. There are various types of generating functions, including ordinary generating functions, exponential generating functions, Lambert series, Bell series, and Dirichlet series; definitions and examples are given below. Every sequence in principle has a generating function of each type (except that Lambert and Dirichlet series require indices to start at 1 rather than 0), but the ease with which they can be handled may differ considerably. The particular generating function, if any, that is most useful in a given context will depend upon the nature of the sequence and the details of the problem being addressed. Generating functions are often expressed in closed form (rather than as a series), by some expression involving operations defined for formal series. These expressions in terms of the indeterminate x may involve arithmetic operations, differentiation with respect to x and composition with (i. e., substitution into) other generating functions; since these operations are also defined for functions, the result looks like a function of x. Indeed, the closed form expression can often be interpreted as a function that can be evaluated at (sufficiently small) concrete values of x, and which has the formal series as its series expansion; this explains the designation "generating functions". However such interpretation is not required to be possible, because formal series are not required to give a convergent series when a nonzero numeric value is substituted for x. Also, not all expressions that are meaningful as functions of x are meaningful as expressions designating formal series; for example, negative and fractional powers of x are examples of functions that do not have a corresponding formal power series. Generating functions are not functions in the formal sense of a mapping from a domain to a codomain. Generating functions are sometimes called generating series, in that a series of terms can be said to be the generator of its sequence of term coefficients.

Функции, генерирующие последовательности полиномов

Идея генерирующих функций может быть расширена на последовательности других объектов. Таким образом, например, полиномиальные последовательности биномиального типа генерируются выражением

где pn(x) — последовательность полиномов, а f(t) — функция определенного вида. Последовательности Шеффера генерируются аналогичным образом. Подробнее см. основную статью «Обобщенные полиномы Апелля».

Программное обеспечение для работы с рекурсивными последовательностями и голономическими генерирующими функциями

Инструменты для обработки и работы с P-рекурсивными последовательностями в Mathematica включают программные пакеты, предоставляемые для некоммерческого использования на сайте RISC Combinatorics Group, посвященном алгоритмической комбинаторике. Несмотря на то, что большая часть кода закрыта, особенно мощные инструменты в этом наборе программ предоставляет пакет Guess для угадывания P-рекурренций для произвольных входных последовательностей (что полезно для экспериментальной математики и исследований) и пакет Sigma, способный находить P-рекурренции для многих сумм и решать P-рекурренции в замкнутой форме, включающие обобщенные гармонические числа. Другие пакеты, перечисленные на этом сайте RISC, ориентированы на работу с голономическими производящими функциями.