1.5. Производящие функции и рекуррентные соотношения.
В результате выполнения алгебраических преобразований могут осуществляться определенные комбинаторные подсчеты. С этим мы уже встретились в 1.2 при выводе биномиальной формулы, когда комбинаторные объекты – числа сочетаний появились в новом качестве биномиальных коэффициентов при выполнении алгебраической операции возведения в степень. Рассмотрим еще примеры, иллюстрирующие эту связь между алгеброй и комбинаторикой.
Пусть в урне находятся 3 красных, 4 синих и 2 зеленых шара. Сколькими способами могут быть извлечены 6 шаров, если считать шары одного цвета между собой неразличимыми? Для ответа на этот вопрос достаточно по обычным алгебраическим правилам раскрыть скобки в выражении
привести подобные члены и взять коэффициент при . Здесь первая скобка соответствует красным шарам, вторая синим и третья зеленым. При перемножении степеней буквы , взятых из различных скобок, показатели степеней складываются, поэтому возникнет столько раз, сколько существует способов выбора 6 шаров. Это рассуждение справедливо не только для , но и для любой другой степени . Выполнив умножение, получаем многочлен
который называется производящей функцией для числа способов выбора, так как коэффициент при равен числу способов выбора шаров. В частности, 6 шаров могут быть извлечены 9 способами.
Несколько видоизменим задачу. Пусть требуется найти число извлечений, содержащих нечетное число красных шаров, четное число синих и хотя бы один зеленый шар. В этом случае также легко выписать производящую функцию, дающую ключ к решению задачи:
Теперь 6 шаров могут быть извлечены лишь двумя способами.
Другой пример. Пусть требуется набрать денежную сумму 10 рублей, имея четыре монеты 1 рубль, три монеты 2 рубля, две монеты 5 рублей и одну монету 10 рублей. Сколькими способами это можно сделать?
в котором каждая скобка соответствует одному из номиналов. Показатели степени, в которые возводится буква в скобке, равны произведению номинала монеты на число монет данного номинала, которое может быть включено в набираемую денежную сумму. Это число изменяется от нуля до количества имеющихся в распоряжении монет данного номинала. Так как при умножении показатели степени складываются, то ответ на вопрос задачи даст после перемножения скобок коэффициент при . Выполнив умножение, получим:
Таким образом, набрать 10 рублей можно пятью способами. Вот они:
Конечно, проще было бы решить задачу, просто указав 5 возможных вариантов, однако полученный в результате перемножения скобок степенной ряд позволяет для любого дать ответ на вопрос, сколькими способами может быть получена денежная сумма в количестве рублей. Он является производящей функцией для числа способов набора денежных сумм.
Производящие функции берут свое начало в работах Муавра, Эйлера и Лапласа. Идея метода производящих функций состоит в том, чтобы сопоставить последовательности решений задачи функцию (степенной ряд), аналитические методы работы с которой оказываются проще и эффективнее комбинаторных методов работы с последовательностями.
Перейдем к формальным определениям. С каждой числовой последовательностью можно связать степенной ряд который называется производящей функцией последовательности. Если ряд сходится в некоторой окрестности нуля, он является рядом Маклорена для функции . Поэтому знание производящей функции позволяет восстановить исходную последовательность:
Полезно знать производящие функции для простейших последовательностей.
Для последовательности, состоящей из единиц ( ), производящая функция
Это есть хорошо известная из школьного курса математики формула для суммы бесконечно убывающей геометрической прогрессии. Почленным дифференцированием из нее получаем, что производящая функция для последовательности ( ) есть
С помощью (k-1) – кратного дифференцирования можно получить и более общую формулу, являющуюся производящей функцией для числа сочетаний с повторениями :
Полезно также следующее непосредственно проверяемое тождество
Теперь, вооруженные уже определенными техническими средствами, перейдем к задачам, решение которых методом производящих функций путем прямого перемножения скобок было бы достаточно утомительным.
Какова вероятность при бросании 4 игральных костей выбросить 14 очков? Эта вероятность равна отношению числа способов выбросить 14 очков к полному числу возможных выпадений 4 различных костей. Подсчет полного числа выпадений 4 различных костей не составляет труда. Так как каждая кость имеет 6 граней, то это число равно . Сложнее найти число способов, которыми может быть выброшено 14 очков. Ответом на этот вопрос является коэффициент при в выражении . Здесь каждая из четырех скобок, возникающих при записи степени в виде произведения, соответствует одной из игральных костей, а степени переменной числу возможных выпадений очков на ней. После выполнения алгебраических преобразований коэффициенты степенного ряда укажут число способов получения любой суммы от 4 до 24. Поэтому полученный степенной ряд (в данном случае конечный) называется производящей функцией для числа способов выпадения различных сумм в четырех бросаниях. Найдем эту производящую функцию.
Легко видеть, что степень возникает в двух случаях: когда в первой сумме , а во второй , и когда в первой сумме , а во второй . Поэтому коэффициент при равен . Таким образом, искомая вероятность равна
Чтобы сравнить возможности различных подходов для решения задач перечисления, рассмотрим задачу из раздела 1.3., решенную там с помощью формулы включения и исключения, и решим её методом производящих функций.
Пусть требуется найти число целочисленных решений системы
Легко понять, что искомое число решений есть коэффициент при после раскрытия скобок в выражении
Более общё, можно сказать, что выписанное выражение является производящей функцией для числа решений системы
так как при любом целом коэффициент при равен числу решений. Найдем коэффициент при :
В коэффициент при дают вклад значения . Поэтому число решений равно
Производящие функции являются мощным средством для решения рекуррентных соотношений, т.е. определении последовательностей, последующие члены которых выражаются через предыдущие. Простейшими рекуррентными последовательностями являются арифметическая и геометрическая прогрессии, у которых каждый последующий член определяется предыдущим, а первый член задается.
Рассмотрим пример рекуррентной последовательности, у которой каждый член, начиная с третьего выражается через два предыдущих, а два первых члена заданы: , , . С помощью рекуррентного соотношения, используя заданные значения и , получаем , и т.д. Воспользовавшись методом производящих функций, найдем в явном виде формулу -го члена.
Домножив обе части рекуррентного соотношения на и просуммировав по , получим
Отсюда для производящей функции
Разрешая его относительно , получаем
Воспользовавшись приведенным выше разложением для , перепишем формулу для в виде
Это позволяет выписать формулу -го члена:
Рассмотрим теперь другой, более интересный пример, показывающий, как рекуррентные соотношения возникают в реальных перечислительных задачах. Пусть требуется найти число двоичных последовательностей длины , не содержащих двух единиц подряд. При имеются две таких последовательности: и . При таких последовательностей три: . Поэтому , .
Разобьем искомое множество последовательностей на 2 подмножества: последовательности, начинающиеся с 0, и последовательности, начинающиеся с 1. Последовательности первого типа не имеют каких-либо дополнительных ограничений на последующие символов. Поэтому их . Последовательности второго типа на второй позиции обязаны содержать 0, а на последующие символов нет каких-либо ограничений, поэтому их . Это приводит к рекуррентному соотношению
т.е. каждый член последовательности, начиная с третьего, равен сумме двух предыдущих членов. Положим . Тогда рекуррентное соотношение будет выполняться, начиная со второго члена. Вместе с начальными данными и оно позволяет найти любой член последовательности . Вот перые семь членов: 1, 2, 3, 5, 8, 13, 21, … . Данная последовательность называется последовательностью Фибоначчи, по имени впервые её рассмотревшего итальянского математика 13 века. Она возникла в придуманной им своеобразной задаче о размножении кроликов.
Для получения формулы -го члена в явном виде домножим обе части рекуррентного соотношения на и просуммируем по от 2 до ∞: