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

САМЫЙ МОЩНЫЙ на сегодняшний день метод работы с последовательностями чисел — это преобразования бесконечных рядов, которые „порождают эти последовательности. Мы уже изучили некоторое количество последовательностей и встречались с производящими функциями; теперь самое время заняться более глубоким изучением производящих функций и убедиться в их исключительной полезности.

7.1 ТЕОРИЯ ДОМИНО И РАЗМЕН

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

Как велико число способов покрытия n-прямоугольника костяшками домино размера Мы будем считать, что все костяшки идентичны (потому, что лежат лицевой стороной вниз, или, может быть, кто-то сделал их неразличимыми, например, покрасив в красный цвет); следовательно, имеет значение только ориентация костяшки — вертикальная или горизонтальная: мы можем представлять себе, что работаем с плитками в форме домино. Например, существует 3 покрытия -прямоугольника, а именно, так что

Чтобы найти общее выражение для в замкнутом виде, мы, как обычно, обратимся к простым начальным случаям. Для существует, очевидно, одно покрытие, 0; когда — имеется два покрытия: и В.

А что можно сказать про случай сколько покрытий возможно здесь? Сразу не ясно, как понимать этот вопрос, но раньше нам уже встречались подобные ситуации. Так, имеется одна перестановка нуля объектов (а именно, пустая перестановка)

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

Рассмотрим еще один простой случай, Имеется две возможности расположения плиток на левом конце прямоугольника — можно положить там либо одну плитку вертикально, либо две горизонтально. Если мы выберем вертикальную плитку, то получим частичное решение и оставшийся -прямоугольник можно покрыть плитками способами. Если же выбрать две горизонтальные плитки, то частичное решение можно завершить способами. Таким образом, (Вот эти пять покрытий: )

Теперь нам известны первые пять значений

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

(Мы считаем это выражением в замкнутом виде для поскольку числа Фибоначчи достаточно важны, чтобы считаться „известными! Кроме того, сами имеют выражение в замкнутом виде (6.123) в терминах алгебраических операций.) Отметим, что это уравнение подтверждает мудрость выбора

Однако при чем здесь производящие функции? Мы как раз приближаемся к тому, чтобы воспользоваться ими, — и это будет еще один способ нахождения Этот способ основан на весьма смелой идее. Рассмотрим „сумму" всех возможных расположений плиток в -прямоугольнике для всех и назовем ее Т:

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

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

Мы уже сложили покрытия, но можем также и умножать их — приписывая одно вслед за другим. Например, умножив на В, получим покрытие Заметьте, однако, что умножение некоммутативно — порядок сомножителей важен: [В отличается от

При таком определении умножения, как легко понять, пустое покрытие играет особую роль — это мультипликативная единица. Например,

Теперь используем арифметику домино для манипулирования с бесконечной суммой Т:

В правых частях этих равенств каждое правильное покрытие содержится ровно по одному разу, так что сделанные нами преобразования имеют смысл, даже несмотря на пренебрежение предостережением из гл. 2 об „абсолютной сходимости! Нижняя строка этого уравнения говорит нам, что любое покрытие в Т есть либо пустое покрытие, либо вертикальная плитка, за которой приписано что-то из Т, либо две горизонтальные плитки, за которыми приписано еще что-то из Т.

Попробуем теперь решить это уравнение относительно Т. Заменив Т в левой части на и вычтя два последних слагаемых из обеих частей уравнения, получим

Для проверки раскроем скобки:

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

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

короткое выражение для Т, нам придется выполнить комбинаторное деление. Слепо доверяя алгебраическим преобразованиям, поделим обе части уравнения (7.3) на и получим

(Умножение некоммутативно, поэтому, не различая левое и правое деление, мы оказываемся на грани жульничества. Однако в данном случае это неважно, поскольку I коммутирует с чем угодно. Но не будем слишком придирчивы, пока наши заумные идеи не привели к парадоксу.)

Следующий шаг — развернуть эту дробь в степенной ряд, используя правило

Пустое покрытие I — мультипликативная единица в нашей комбинаторной арифметике — будет играть роль обычной мультипликативной единицы 1, а вместо z используем Получим разложение

Это действительно Т, однако покрытия расположены в другом порядке, чем мы записывали ранее. Каждое покрытие встречается в этой сумме ровно один раз; так, содержится в .

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

Здесь слагаемое представляет два члена старого разложения [В и В], имеющих по одному вертикальному и по два горизонтальных домино; аналогично, представляет три члена По-существу, мы рассматриваем и о как обычные (коммутирующие) переменные.

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

(На последнем шаге мы заменили на это допустимо, поскольку при Мы заключаем таким образом, что есть число способов покрытия -прямоугольника с помощью вертикальных и горизонтальных домино. Так, мы только что рассматривали покрытие -прямоугольника, включающее 4 вертикальные и горизонтальных плиток; всего имеется таких покрытий, следовательно, одним из членов в коммутативном варианте Т будет

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

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

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

Помимо прочего, из нашего исследования можем заключить, что число покрытий -прямоугольника ровно парами горизонтальных домино составляет (Действительно, в покрытии будет вертикальных домино, следовательно, в соответствии с нашей формулой найдется

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

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

Попробуем подняться еще на одну ступень, занявшись задачей, где угадать ответ будет выше наших сил. Сколько существует способов покрыть костяшками домино -прямоугольник (обозначим это число

Кое-что можно узнать, проанализировав начальные случаи. Пустое покрытие дает . Для не существует допустимых покрытий, поскольку одна -плитка не заполняет -прямоугольник, а для двух нет места. Следующий случай, легко анализируется вручную: имеется три покрытия так что (Мы на самом деле уже знали это, поскольку из предыдущей задачи известно, что а способов покрытия -прямоугольника ровно столько же, сколько и для -прямоугольника.) Для как и для нет покрытий. В этом можно убедиться, либо быстренько перебрав все варианты, либо же взглянув на проблему с более высокого уровня: площадь -прямоугольника нечетна, так что его, наверное, не удастся покрыть домино с четной площадью. (Очевидно, что те же рассуждения применимы в случае любого нечетного Наконец, когда имеется, вроде бы, около дюжины покрытий; чтобы найти точное число, надо потратить изрядное время, проверяя полноту списка.

Испробуем поэтому подход с бесконечной суммой, который успешно сработал в прошлый раз:

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

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

состоит из всех покрытий прямоугольника без левого верхнего угла. Ряд А представляет собой зеркальное отражение V. Эти разложения позволяют записать

Точно так же разлагаются сами V и А, поскольку входящие в них покрытия могут начинаться лишь двумя способами:

Теперь мы имеем три уравнения с тремя неизвестными . Их можно решить, выразив сначала V и А через и подставив результаты в уравнение для

Это последнее уравнение можно решить относительно получив компактную формулу

Это выражение определяет так же, как (7.4) определяет Т.

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

(Этот вывод заслуживает тщательной проверки. На последнем шаге использована формула тождество (5.56).) Посмотрим внимательно на нижнюю строку и

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

Теперь мы в состоянии проанализировать -покрытия, что вызвало затруднения в начале нашего исследования задачи Если то общая площадь равна 12, поэтому всего потребуется домино. Из них будет вертикальных и к горизонтальных костяшек для некоторых следовательно, Иначе говоря, к Если вертикальные костяшки не использовать вообще, то число вариантов равно (Здесь мы учли покрытие .) Если мы используем две вертикальные плитки, то всего имеется таких покрытий. Если, наконец, использовать 4 вертикальные плитки, то таких покрытий а всего покрытий будет В общем случае для четного те же рассуждения показывают, что следовательно, и °бщее число -покрытий равно

Как и ранее, можно заменить оба символа на получая производящую функцию без дискриминации домино по их убеждениям. Результатом будет функция

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

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

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

Сколько существует способов заплатить 50 центов? Мы считаем, что платить можно пенни никелями даймами

четвертями и полудолларами . Дьёрдь Пойа [243] популяризовал эту задачу, продемонстрировав поучительный способ ее решения с помощью производящих функций.

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

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

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

Аналогично, если допустить еще и даймы, то получим бесконечную сумму

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

Наша задача состоит в том, чтобы найти, сколько слагаемых в С стоят ровно 50 центов.

Задача решается с помощью простого трюка. Заменим на на на на на . Каждое слагаемое тогда заменится на , где — стоимость исходного слагаемого в пенни. Например, слагаемое превратится в Каждый из четырех возможных способов заплатить 13 центов, а

именно, сведется к следовательно, коэффициентом при после z-подстановки будет 4.

Пусть обозначают число способов заплатить сумму в центов, если можно использовать монеты не старше, соответственно, 1,5, 10, 25 и 50 центов. Наш анализ показал, что эти числа суть коэффициенты при в соответствующих степенных рядах

Очевидно, что для всех По кратком размышлении легко доказать, что для того чтобы составить сумму в центов из пенни и никелей, мы должны взять 0, или 1, или или никелей, после чего останется лишь единственный способ выбрать требуемое число пенни. Итак, значения легко вычисляются, однако с дело обстоит гораздо сложнее.

Один из подходов к исследованию этих формул основан на замечании, что есть просто Следовательно, мы можем записать

Умножая на знаменатель, получим

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

Например, коэффициент при равен поэтому должно быть как и записано выше.

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

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

В самом низу таблицы находится ответ имеется ровно 50 способов дать 50 центов

А что можно сказать о замкнутой форме для Перемножение всех уравнений дает нам компактное выражение

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

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

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

разбиений пятерки, а именно,

следовательно, (Кроме того, судя по началу, все простые числа. Однако и замечательная гипотеза гибнет.) Для неизвестно выражение в замкнутом виде, однако теория разбиений представляет собой захватывающую область математики, в которой было сделано немало замечательных открытий. Например, Рамануджан, выполнив остроумные преобразования производящих функций, доказал, что (см. Эндрюс [386, гл. 10]).