Производящая функция последовательности {an}, n>=0 – формальный степенной ряд:
Переход от последовательностей к их производящим функциям позволяет заменить операции над последовательностями операциями над их производящими функциями.
Идея метода производящих функций состоит в том, что рекуррентное соотношение, определяющее последовательность {an}, переписывают как уравнение для ее производящей функции, это уравнение решают и по найденной производящей функции получают зависимость общего члена последовательности {an} от n.
Для того, чтобы получить алгебраические выражения для значения каждой переменной в зависимости от номера итерации необходимо преобразовать операции, изменяющие значения переменных, в рекуррентные соотношения вида:
t – функция преобразования переменной v, принадлежащая множеству T
Vi-1 – значения переменных, полученные на предыдущей итерации
Vi – значения переменных, полученные на текущей итерации
Производящие функции (или выражения для vi) достаточно просто можно получить для присваиваний вида:
В этом случае для получения выражения для vi достаточно подставить выражения для всех остальных переменных в правую часть или найти производящую функцию для f.
Пользуясь методикой из [2] каждый оператор присваивания вида
где Fv(z) – производящая функция для переменной v
FV – множество производящих функций для переменных, принадлежащих множеству V
G – некоторая алгебраическая функция
Найти алгебраическое выражение (возможно содержащее в себе другие производящие функции) для производящей функции для f можно пользуясь линейностью производящих функций: производящая функция суммы равняется сумме производящих функций.
Для каждого из слагаемых существует следующий выбор: