5.4 ПРОИЗВОДЯЩИЕ ФУНКЦИИ

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

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

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

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

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

другими словами, означает коэффициент при в разложении

Пусть — производящая функция для последовательности как в (5.52), и пусть — производящая функция

для другой последовательности Тогда произведением является степенной ряд

с коэффициентами при

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

и если известны производящие функции то

Последовательность определенная по правилу (5.54), называется сверткой последовательностей — две последовательности „свертываются", образуя суммы произведений всех тех элементов последовательностей, нижние индексы которых при сложении дают некоторую определенную величину. Суть предыдущего абзаца состоит в том, что свертка последовательностей соответствует умножению их производящих функций.

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

Аналогично,

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

А теперь наступает кульминационный момент: приравнивание коэффициентов при в обеих частях этого равенства дает

и мы переоткрыли правило свертки Вандермонда (5.27)!

Так просто и славно — давайте попробуем еще. На этот раз воспользуемся выражением которое для последовательности

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

Приравнивание коэффициентов при приводит теперь к равенству

Не мешало бы проверить это на одном-двух простых случаях. Так, при получаем

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

Таким образом, при равенство (5.55) подтверждается как нельзя лучше. Оказывается, что (5.30) — это частный случай нового тождества (5.55).

Биномиальные коэффициенты появляются также и в некоторых других производящих функциях — особенно примечательны следующие важные соотношения, в которых нижний индекс остается фиксированным, а верхний — изменяется:

Здесь второе соотношение — это всего лишь первое, умноженное на , т. е. „сдвинутое вправо" на . А первое соотношение — это всего слегка замаскированный частный случай биномиальной теоремы: если в соответствии с (5.13) разложить то коэффициентом при является который может быть переписан в виде или в виде после обращения верхнего индекса. Эти частные случаи заслуживают явного упоминания, поскольку они довольно часто возникают в приложениях.

При получаем частный случай этого частного случая — геометрический ряд

Это производящая функция для последовательности и она особенно полезна потому, что свертка любой другой последовательности с данной представляет собой последовательность сумм: если при любом к, то (5.54) сводится к

Поэтому, если — производящая функция для членов суммы то — производящая функция для их сумм .

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

может быть представлена в виде свертки, если выразить через факториалы и разделить обе части на

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

то данная свертка/рекуррентность указывает на то, что

Разрешая это относительно получаем

Приравнивание коэффициентов при показывает теперь, что

а это является той самой формулой, которая была выведена ранее путем обращения.

До сих пор наши упражнения с производящими функциями приводили к тонким доказательствам того, что мы и так умели получать более грубыми методами — мы не получили никаких новых результатов, за исключением (5.55). Теперь мы намерены установить нечто новое и даже удивительное. Существуют два семейства степенных рядов, которые порождают особенно обширный класс тождеств с биномиальными коэффициентами. Определим обобщенный биномиальный ряд и обобщенный экспоненциальный ряд следующим образом:

Мы покажем в разд. 7.5, что данные функции удовлетворяют соотношениям

В частном случае имеем

это объясняет, почему ряды с произвольным параметром называются „обобщенными" биномиальным и экспоненциальным рядами.

Следующие пары соотношений справедливы при любом вещественном

(Если то нужно проявить некоторую осторожность относительно того, как интерпретировать коэффициент при — каждый такой коэффициент является многочленом относительно . К примеру, постоянным членом ряда является а это равно 1 даже при

Поскольку уравнения (5.60) и (5.61) справедливы при любом то можно получить весьма общие соотношения, если перемножить ряды, которые соответствуют различным степеням

Таблица 229. Общие соотношения свертки, справедливые при целом

Так,

Этот степенной ряд должен быть равен

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

справедливое при любых вещественных При это тождество сводится к свертке Вандермонда. (Если же в этой формуле случайно обращается в нуль, то множитель в знаменателе следует рассматривать как сокращающийся с в числителе биномиального коэффициента. Обе части данного соотношения являются многочленами относительно Аналогичные соотношения имеют место при умножении на и т. д. - их сводка представлена в табл. 229.

Мы уже научены тому, что вообще-то неплохо рассмотреть частные случаи общих результатов. Например, что случится, если положить Обобщенный биномиальный ряд весьма прост — это всего лишь

так что ничего не добавляет к тому, что нам уже известно из свертки Вандермонда. Но — это важная функция

которая еще не встречалась, - она удовлетворяет основному соотношению

Эта функция, впервые изученная Эйлером [381] и Эйзенштейном [362], возникает во многих приложениях [401, 229].

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

Коэффициенты в называются числами Каталана по имени Эжена Каталана, написавшего о них основополагающую работу в 30-х годах прошлого столетия [127]. Последовательность этих чисел начинается следующим образом:

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

Завершим этот раздел выводом важного следствия из (5.72) и (5.73) - соотношения, выявляющего дополнительные связи между функциями

Данное соотношение справедливо потому, что в случае коэффициенты при в разложении имеют вид

Все члены чудненько сокращаются друг с дружкой. Теперь можно воспользоваться соотношениями (5.68) и (5.69), чтобы выразить сумму в замкнутой форме:

(Частный случай возникал в задаче 3 из разд. 5.2. Поскольку числа являются корнями шестой степени из единицы, то суммы вида обнаруживают периодическое поведение, что наблюдалось нами в той задаче.) Аналогично можно объединить (5.70) и (5.71), с тем чтобы избавиться от громоздких коэффициентов, получая