7.6 ЭКСПОНЕНЦИАЛЬНЫЕ ПРОИЗВОДЯЩИЕ ФУНКЦИИ

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

экспоненциальной производящей функцией или ЭПФ последовательности Прилагательное „экспоненциальная употреблено потому, что функция экспоненты есть ЭПФ последовательности

Многие из производящих функций в табл. 386 есть на самом деле ЭПФ. Например, уравнение (7.50) говорит нам, что

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

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

это ЭПФ последовательности

Дифференцирование ЭПФ последовательности по z дает

это ЭПФ последовательности Таким образом, дифференцирование соответствует операции сдвига влево для обычных производящих функций. (Мы использовали это свойство когда занимались гипергеометрическими рядами Интегрирование дает

т. е. сдвиг вправо, последовательности

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

Биномиальные коэффициенты появляются здесь из-за того, что следовательно,

другими словами, обычная свертка последовательностей

Биномиальные свертки часто встречаются в приложениях. Так, в (6.79) мы определили числа Бернулли посредством неявного рекуррентного соотношения

это соотношение можно переписать в виде биномиальной свертки, если заменить на и добавить к обеим частям

Теперь можно перевести это соотношение на язык степенных рядов (как было обещано в гл. 6), если ввести в рассмотрение ЭПФ для чисел Бернулли, Левая часть (7.76) есть биномиальная свертка с постоянной последовательностью таким образом, ЭПФ левой части равна Для правой части экспоненциальной производящей функцией является Следовательно, должно выполняться тождество ; мы доказали равенство (6.81), которое встречается также в табл. 386 как формула (7.44).

А теперь займемся вновь суммой, неоднократно появляющейся в этой книге:

На сей раз попробуем применить к этой задаче производящие функции: вдруг это упростит дело. Будем считать фиксированным, переменным; наша задача, таким образом, - разобраться с поведением коэффициентов степенного ряда

Мы знаем, что производящая функция последовательности равна

следовательно,

если поменять местами порядок суммирования. Эту сумму можно записать в замкнутом виде:

но мы абсолютно ничего не знаем о разложении подобной замкнутой формулы по степеням

На выручку приходят экспоненциальные производящие функции. Для последовательности равна

Для получения коэффициентов воспользуемся известной последовательности а именно,

и найдем

Последняя же сумма есть сумма геометрической прогрессии, имеющая замкнутый вид

Эврика! Все, что нам остается сделать, — это выписать коэффициенты этой сравнительно простой функции, и мы получим выражение для поскольку

Здесь вступают в игру числа Бернулли. Совсем недавно мы заметили, что ЭПФ для чисел Бернулли есть

следовательно, можно записать

Сумма равняется коэффициенту при в этой функции, умноженному на Например,

Таким образом, мы в очередной раз вывели формулу и это самый простой вывод из всех: при помощи нескольких строк найдено поведение при любых т.

Можно записать общую формулу

где — многочлен Бернулли, определяемый как

Вот почему это так: многочлен Бернулли является биномиальной сверткой последовательности следовательно, экспоненциальная производящая функция для есть произведение ЭПФ этих последовательностей,

Отсюда вытекает равенство (7.79), поскольку ЭПФ для есть, по (7.78),

Обратимся теперь еще к одной задаче, где ЭПФ есть как раз то, что нужно: сколько существует остовных деревьев в полном графе с вершинами Обозначим это число Полный граф содержит ребер, по одному ребру, соединяющему каждую пару различных вершин; так что мы, по существу, ищем полное число способов соединить данных объектов, проведя линий между ними.

Имеем Кроме того, поскольку полный граф с тремя вершинами есть фан порядка 2; мы знаем, что

в случае имеется 16 остовных деревьев:

Следовательно,

Опыт работы с аналогичной задачей для фанов подсказывает, что наилучший способ справиться с этой задачей состоит в том, чтобы выделить одну вершину и посмотреть на те связные компоненты или блоки, на которые разобьется остовное дерево, если проигнорировать все ребра, проходящие через выделенную вершину. Если невыделенные вершины образуют компонент размеров то их можно соединить с выделенной вершиной способами. Например, в случае можно считать выделенной нижнюю левую вершину. В верхнем ряду (7.82) изображены случаев, когда три остальные вершины соединены между собой одним из способов и затем соединены с левой нижней вершиной одним из трех способов. В нижнем ряду изображены решений, в которых остальные три вершины разбиты на компоненты размеров 2 и 1 одним из способов; там же показан случай где три остальные вершины полностью изолированы.

Подобные рассуждения приводят к рекуррентному соотношению

при любом Действительно, имеется способов представить элементов в виде последовательности из компонент размеров, соответственно, имеется способов соединить вершины внутри этих компонент какими-то остовными деревьями; имеется способов соединить вершину с этими компонентами; и мы делим на поскольку не должны учитывать порядок компонент. Например, для это рекуррентное соотношение дает

Рекуррентное соотношение для выглядит на первый взгляд устрашающе, на самом же деле оно не столь уж плохо, только

слегка свернуто. Обозначим

и тогда все существенно упростится:

Внутренняя сумма представляет собой коэффициент при в ЭПФ , возведенной в степень; формула будет правильной и для если добавить слагаемое отвечающее случаю Итак,

при любом и мы получаем уравнение

Это прогресс! Уравнение (7.84) выглядит почти так же, как уравнение

определяющее обобщенный экспоненциальный ряд и (7-71); и действительно, имеется связь между этими функциями:

Таким образом, мы можем просто прочитать ответ к нашей задаче:

При любом полный граф с вершинами имеет ровно остовных деревьев.