Глава 3. Методы подсчета и оценивания

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

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

Пусть — произвольная последовательность. Сопоставим последовательности функцию действительного или комплексного переменного:

Функция называется производящей функцией последовательности Как правило, поиск функции по формуле (3.1.1) прямыми методами является сложной задачей. Однако заметим, что последовательность может быть восстановлена по Выражение (3.1.1) является разложением в ряд Тейлора в окрестности точки Воспользуемся этим замечанием и приведем некоторые наиболее распространенные производящие функции и соответствующие им последовательности.

(см. скан)

Задача. Найти число -мерных граней в -мерном кубе. Решение. Обозначим через число -мерных граней в -мерном кубе, где Тогда производящую функцию последовательности можно записать как Индекс для показывает размерность куба. Например, Рассмотрим производящую функцию последовательности для куба. Заметим, что куб можно получить из -мерного куба сдвигом последнего по измерению. На рисунке показан пример получения трехмерного куба сдвигом по третьему измерению квадрата (двухмерного куба). Отсюда видно, что -мерный куб включает два старых -мерных куба и каждая -мерная грань при сдвиге переходит в -мерную грань. Из приведенных рассуждений следует, что

Отсюда

Воспользуемся разложением бинома Ньютона:

Сравнивая коэффициенты при степенях получим, что число -мерных граней в -мерном кубе равно Например,

Простейшие производящие функции (3.1.2)-(3.1.9) будем использовать как «строительные кирпичики» для получения производящих функций более сложных последовательностей. С этой целью рассмотрим наиболее важные из операций над производящими функциями, т.е. способы получения новых производящих функций и соответствующих им последовательностей. Обозначим через последовательности, а соответствующие им производящие функции —

3.1.1. Линейные операции

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

Например, последовательность соответствует производящей функции , а последовательность соответствует производящей функции тогда последовательность соответствует производящей функции .

3.1.2. Сдвиг начала вправо

Пусть последовательность определяется через последовательность следующим образом:

Действительно

3.1.3. Сдвиг начала влево

Пусть последовательность определяется через последовательность следующим образом: тогда

Действительно

3.1.4. Частичные суммы

Пусть последовательность определяется через последовательность следующим образом:

Действительно

Множество пар точек по которым ведется суммирование, представлено на рисунке. Изменим порядок суммирования (сначала по затем по k). Выражение для примет вид

3.1.5. Дополнительные частичные суммы

Пусть последовательность определяется через последовательность следующим образом:

Действительно

Множество пар точек по которым ведется суммирование, представлено на рисунке. Изменим порядок суммирования (сначала по затем по k). Выражение для примет вид

3.1.6. Изменение масштаба

1. Пусть последовательность определяется через последовательность следующим образом:

Действительно

или

2. Пусть последовательность определяется через последовательность следующим образом:

Поскольку , то

3.1.7. Свертка

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

Действительно, , тогда

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

Задача. Рассмотрим обобщенное биномиальное правило раскрытия выражений.

где обобщенный биномиальный коэффициент

Тогда

Рассмотрим полученное выражение при

Таким образом,

Рассмотрим выражение при

где

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

Задача. Сколькими способами можно разбить выпуклый -угольник на треугольники диагоналями, не пересекающимися внутри многоугольника?

Решение. Пусть искомое число способов разбить -угольник на треугольники. Перенумеруем вершины исходного многоугольника числами от 1 до Заметим, что при любом разбиении найдется треугольник, содержащий ребро многоугольника с вершинами Третья вершина этого треугольника может быть любой из остальных Пусть это будет вершина k. Если удалить треугольник с вершинами , то получим два многоугольника с числом вершин к и

которые можно разбить на треугольники способами. Суммируя по получим (согласно правилам прямого произведения и суммы) искомое число разбиений исходного -угольника на треугольники:

где и положили

Получили нелинейное рекуррентное соотношение для последовательности для поиска которой удобно ввести новую последовательность такую, что Тогда рекуррентное соотношение перепишется в виде

Заметим, что правая часть является сверткой двух одинаковых последовательностей (см. п.3.1.7 операций с производящими функциями). Ввиду этого, составим производящую функцию правой части

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

Отсюда

Ранее рассмотренное разложение обобщенного бинома

запишем для случая

Поскольку результат должен быть рядом по неотрицательным степеням то решение является посторонним. Окончательно

Отсюда

Ответ: число способов разбить выпуклый -угольник на треугольники непересекающимися диагоналями равно

Задача. Найти сумму .

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

Для решения задачи необходимо найти . С этой целью определим что позволит нам установить значения Последовательности связаны «изменением масштаба», значит Последовательности также связаны «изменением масштаба», следовательно,

Последовательности связаны «частичной суммой», тогда

Окончательно

Для получения коэффициентов воспользуемся разложением (3.1.9):

Теперь можно записать, что

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

Таким образом,

Задача. Показать, что или

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

Рассмотрим последовательность Так как связаны частичной суммой, то Разложение (3.1.9) позволяет записать последнее выражение в следующем виде:

Задача. Пусть целочисленные случайные величины и определены их ряды распределений. Характеристической функцией распределения случайной величины называется функция

Таким образом, это производящая функция последовательности чисел где Будем полагать независимыми случайными величинами Рассмотрим Очевидно, что

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