1.5. Производящие функции

1.5.1. Общие сведения о производящих функциях

Для решения комбинаторных задач могут быть использованы методы математического анализа. Основой этого служит метод производящих функций. Этот метод позволяет достичь изучения свойств последовательностей. Он применяется для перечисления комбинаторных чисел и для установления комбинаторных тождеств.

Исходным пунктом этого метода является последовательность комбинаторных чисел {a_k} и последовательность базисных функций .

Рассмотрим формальный ряд

В частности, если последовательность конечна, т.е. , то ряд представляет собой многочлен. При определенных ограничениях, ряд будет сходиться и тогда, в некоторой области он будет задавать функцию

Функция F(x) называется производящей функцией для заданной последовательности комбинаторных чисел {a_k} относительно заданной базисной последовательности функций .

Наиболее часто в качестве базисной рассматривается последовательность , (k = 0,1,..). Получающиеся при этом производящие функции называются обычными. Т.е. обычные производящие функции имеют вид:

В комбинаторном анализе используются также экспоненциальные производящие функции

.

Для производящих функций по аналогии со сходящимися рядами определяются операции сложения, умножения, дифференцирования, интегрирования и т.д. при этом x является действительной или комплексной переменной. При выполнении условий сходимости производящие функции являются аналитическими.

Рассмотрим ряд примеров.

1.5.2. Производящая функция для биноминальных коэффициентов

Получим производящую функцию для конечной последовательности чисел, представляющих собой различное число сочетаний изn элементов -– . Известно, что

и

Эти равенства являются частными случаями более общей формулы, дающей разложение для . Запишем в виде

Раскроем скобки в правой части этого равенства, причем будем записывать все множители в том порядке, в котором они нам встретятся. Например, запишем в виде:

а - в виде:

Видно, что в верхнюю формулу входят все размещения с повторениями, составленные из букв и по две буквы в каждом размещении, а в нижнюю формулу - размещения с повторениями из тех же букв, но состоящие из трех букв каждое. То же самое и в общем случае — после раскрытия скобок в формуле мы получим всевозможные размещения с повторениями букв и , состоящие из элементов. Приведем подобные члены. Подобными будут члены, содержащие одинаковое количество букв (тогда и букв в них будет поровну). Найдем, сколько будет членов, в которые входит букв и, соответственно, букв . Эти члены являются перестановками с повторениями, составленными из букв и букв . Поэтому их число равно

Отсюда вытекает, что после приведения подобных членов выражение войдет с коэффициентом . Итак, мы доказали, что

Это равенство принято называть формулой бинома Ньютона. Если положить в этом равенстве , то получим

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

Пусть , (k=0,1,…,n)

Тогда

В данном случае в качестве производящей функции выступает бином Ньютона .

Используя заданную производящую функцию, докажем тождество:

Для этого возьмем тождество

Они эквивалентны следующему

Сравнивая коэффициенты при xⁿ, получим