Производящие функции — туда и обратно

в 20:00, , рубрики: Алгоритмы, комбинаторика, математика, числа фибоначчи, метки: , , ,

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

Введение

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

Идея производящих функций достаточно проста: сопоставим некоторой последовательности <g0, g1, g2, ..., gn> — дискретному объекту, степенной ряд g0 + g1z + g2z2 +… + gnzn +… — объект непрерывный, тем самым мы подключаем к решению задачи целый арсенал средств математического анализа, который как мы все знаем очень большой.

Вышесказанное можно записать с помощью математических формул следующим образом: <g0, g1, g2, ..., gn> <=> g0 + g1z + g2z2 +… + gnzn +…. Обычно говорят, последовательность генерируется, порождается производящей функцией. Важно понимать, что это символьная конструкция, то есть вместо символа z может быть любой объект, для которого определены операции сложения и умножения.

История возникновения производящих функций

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

В 50-х годах XVIII века Эйлер решал следующую задачу: какие грузы можно взвесить с помощью гирь в 20, 21, 22,..., 2n грамм и сколькими способами? При решении этой задачи он использовал никому неизвестный на то время метод производящих функций, которому и посвящена данная статья. К этой задаче мы вернемся немного позже, после того как разберемся более подробно с устройством производящих функций.

Метод производящих функций

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

Обозначим белый шар символом ○, черный — ●, Tn — искомое количество расположений шаров, общее количество которых равно n. Символом Ø обозначим нулевое количество шаров. Как и любое решение комбинаторной задачи начнем с тривиальных случаев:

Если n = 1, то очевидно имеется 2 способа — взять либо белый шар ○, либо взять черный шар ●, таким образом, T2 = 2.

Если n = 2, то имеется 4 способа расположений: ○○, ○●, ●○, ●●.

Рассмотрим случай для n = 3. Мы можем начать белым шаром и продолжить 4-мя комбинациями, описанными выше ○○○, ○○●, ○●○, ○●●, или же мы можем начать черным шаром и аналогично продолжить 4-мя способами ●○○, ●○●, ●●○, ●●●.

В итоге количество шаров удвоилось, то есть T3 = 2T2. Аналогично T4 = 2T3, то есть, обобщая для всех n получаем рекуррентное уравнение Tn = 2Tn-1 которое и является решением для данной задачи. Решение такого уравнения можно легко угадать — Tn = 2n (так как 2⋅2n-1 = 2n).

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

«Просуммируем» все возможные комбинации расположений шаров:

G = Ø + ○ + ● + ○○ + ○● + ●○ + ●● + ○○○ + ○○● + ○●○ + ○●● + ●○○ + ●○● + ●●○ + ●●● +…

Вопрос о справедливости такой нелепой на первый взгляд суммы опустим. Будем складывать и умножать последовательности шаров. Со сложением все понятно, но что значит умножение шаров? Перемножив ○● на ●○ мы получим не что иное как ○●●○. Заметим, однако, что произведение шаров в отличие от произведения чисел не является коммутативным, то есть ○●⋅●○ ≠ ●○⋅○●. Символ Ø — в произведении играет роль мультипликативной единицы, то есть Ø ⋅ ○○● = ○○● ⋅ Ø = ○○●.

Произведем с рядом G последовательность манипуляций, а именно вынесем за скобки белый и черный шары:

G = Ø + ○ (Ø + ○ + ● + ○○ + ○● + ●○ + ●● + ...) + ● (Ø + ○ + ● + ○○ + ○● + ●○ + ●● + ...) = Ø + ○G +●G.

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

В этой сумме так же учтены все возможные варианты разбиения в точности по одному разу, просто в другом порядке.

Далее воспользуемся формулой бинома Ньютона: Производящие функции — туда и обратно, где Производящие функции — туда и обратно — число сочетаний из n по k.

Тогда с учетом этого имеем: Производящие функции — туда и обратно.

Коэффициент при ○kn-k равен Производящие функции — туда и обратно показывает общее количество последовательностей из n шаров содержащих ○ шары в количеств k штук и ● шары в количестве n-k штук. Как известно Производящие функции — туда и обратно.

Эту формулу можно было получить непосредственно из Производящие функции — туда и обратно заменив Ø на 1, а ○ и ● на z (так как цвет шара не играет роли). Получим Производящие функции — туда и обратно, то есть коэффициент при zn равен 2n.

Обсуждение метода

Так что же позволяет данному методу быть работоспособным при решении различных задач?

Алгоритм решения задачи можно описать примерно следующим образом: рассматривается некоторая бесконечная сумма, которая в конечном итоге представляет собой формальный степенной ряд G(z) = g0 + g1z + g2z2 +… + gnzn +… причем коэффициенты gk — являются ключом к решению исходной задачи. Тот факт, что ряд является формальным, говорит о том, что z — является просто символом, вместо него может быть любой объект: число, шар, кость домино и т.д. В отличие от степенных рядов в анализе формальным степенным рядам не придается числовых значений и, соответственно, нет смысла говорить о сходимости таких рядов для числовых аргументов.

G(z) = g0 + g1z + g2z2 +… + gnzn +… — называется производящей функцией для последовательности чисел <g0, g1, g2, ..., gn>. Заметим, однако, что хотя G(z) — функция, это всё таки формальная запись, то есть мы не можем подставить вместо z значение z = z0, за исключением z = 0, так как G(0) = g0.

Затем производя различные преобразования с бесконечной суммой G(z) мы преобразуем её к замкнутому (компактному) виду. То есть у производящей функции есть 2 представления: бесконечное и замкнутое и, как правило, для решения задачи необходимо бесконечный вид преобразовать к замкнутому.

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

Отвечая на поставленный вначале вопрос можно сказать так: успех данного метода связан с возможностью записать производящую функцию в замкнутом виде. Так, например, производящая функция для последовательности <1, 1, 1, ..., 1> в бесконечном виде представляется как 1 + x + x2 + x3 + ..., а в замкнутом Производящие функции — туда и обратно.

А теперь вооружившись знаниями, вернемся к задаче, которую решал Эйлер.

Итак, задача звучит следующим образом: какие грузы можно взвесить с помощью гирь в 20, 21, 22,..., 2n грамм и сколькими способами?

Я не знаю, как долго Эйлер придумывал решение для этой задачи, но оно поражает своей неожиданностью. Посудите сами. Эйлер рассматривает произведение G(z) = (1+z)(1+z2)(1+z4)(1+z8)… которое после раскрытия скобок представляется в виде бесконечного ряда G(z) = g0 + g1z + g2z2 +… + gnzn +….

Что же из себя представляют коэффициенты gk? Каждый gk — это коэффициент при zk, а zk — получается как произведение каких-то одночленов z2m, то есть gk — это в точности число разных представлений числа k в виде суммы некоторых из чисел 20, 21, 22, 23,...,2m,…. Другими словами gk — это число способов взвешивания груза в k грамм заданными гирями. Как раз то, что мы искали!

Следующий шаг Эйлера не менее удивителен. Он умножает обе части равенства на (1-z).

Производящие функции — туда и обратно
С одной стороны G(z) = g0 + g1z + g2z2 +… + gnzn +… с другой стороны мы только что получили G(z) = Производящие функции — туда и обратно. Но ведь Производящие функции — туда и обратно. Сопоставляя эти два равенства, получаем g1 = g2 = g3 =… = 1, то есть любой груз в k грамм можно взвесить гирями в 1, 2, 4, 8,… грамм притом единственным способом.

Вот так вот Эйлер применил метод производящих функций при решении задач.

Решение рекуррентных соотношений

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

Начнем со всеми знакомой последовательностью чисел Фибоначчи. Каждый из нас знает ее рекуррентный вид: F0 = 0, F1 = 1, Fn = Fn-1 + Fn-2 ,n ≥ 2. Однако не каждый знает вид этой формулы в замкнутом виде и это не удивительно, ведь она содержит иррациональное число в своем составе (кстати, это число есть не что иное как «золотое сечение»).

Итак, имеем

F0 = 0,
F1 = 1,
Fn = Fn-1 + Fn-2, n ≥ 2

Умножим каждую строчку на z0, z1, ..., zn соответственно:

z0 ⋅ F0 = 0,
z1 ⋅ F1 = z,
zn ⋅ Fn = zn ⋅ Fn-1 + zn ⋅ Fn-2 ,n ≥ 2

Просуммируем эти равенства:

Производящие функции — туда и обратно

Обозначим левую часть Производящие функции — туда и обратно

Рассмотрим каждое из слагаемых в правой части:

Производящие функции — туда и обратно

Имеем следующее уравнение:

Производящие функции — туда и обратно
решая которое относительно G(z) находим Производящие функции — туда и обратно — производящая функция для последовательности чисел Фибоначчи. Следующим шагом является ее разложение в степенной ряд, а для этого разложим ее на сумму простейших дробей.
Корни уравнения 1 — z — z2 = 0 — Производящие функции — туда и обратно
Тогда нашу производящую функцию можно разложить следующим образом:

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

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

Производящие функции — туда и обратно находим Производящие функции — туда и обратно.

Но ведь мы искали G(z) в виде Производящие функции — туда и обратно. Отсюда делаем вывод, что

Производящие функции — туда и обратно

Эту формулу можно переписать в другом виде не используя «золотое сечение»:

Производящие функции — туда и обратно,
что достаточно трудно было ожидать, учитывая красивое рекуррентное уравнение.

Давайте запишем общий алгоритм решения рекуррентных уравнений, используя производящие функции. Он записывается в 4 шага:

  1. Запишите одно уравнение, выражающее gn через другие элементы последовательности. Это уравнение должно оставаться справедливым для всех целых n с учетом того, что g-1=g-2=....=0.
  2. Умножьте обе части уравнения на zn и просуммируйте по всем n. В левой части получится сумма Производящие функции — туда и обратно, которая равна производящей функции G(z). Правую часть следует преобразовать так, чтобы она превратилась в какое-то другое выражение, включающее G(z).
  3. Решите полученное уравнение, получив для G(z) выражение в замкнутом виде.
  4. Разложите G(z) в степенной ряд и прочитайте коэффициент при zn, это и будет замкнутый вид для gn.

Причина работоспособности этого метода в том, что единая функция G(z) представляет всю последовательность gn и это представление допускает многие преобразования.

Давайте для закрепления алгоритма рассмотрим еще один пример (более сложный). Пусть надо решить такое рекуррентное уравнение:

g0 = 1,
g1 = 1,
gn = gn-1 + 2gn-2 + (-1)n

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

n 0 1 2 3 4 5 6
gn 1 1 4 5 14 23 52

Будем следовать вышеописанному алгоритму. Первое условие алгоритма выполнено. Умножим обе части всех равенств на z в соответствующей степени и просуммируем:

z0⋅g0 = 1,
z⋅g1 = z,
zn⋅gn = zn⋅gn-1 + 2zn⋅gn-2 + (-1)n⋅zn

Производящие функции — туда и обратно

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

Попытаемся выразить правую часть через G(z). Рассмотрим каждое слагаемое:

Производящие функции — туда и обратно

Составляем уравнение:

Производящие функции — туда и обратно

Это и есть производящая функция для заданного рекуррентного уравнения в замкнутом виде. Раскладывая её на простейшие дроби (например, методом неопределенных коэффициентов или методом подстановки различных значений z), получаем:

Производящие функции — туда и обратно

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

Производящие функции — туда и обратно

Собственно все. Раскладываем каждое слагаемое в степенной ряд и получаем ответ:

Производящие функции — туда и обратно

С одной стороны мы искали G(z) в виде Производящие функции — туда и обратно, с другой стороны Производящие функции — туда и обратно.

Значит, Производящие функции — туда и обратно.

Попробуйте решить такое рекуррентное уравнение:

g0 = 1,
g1 = 2,
gn = 6gn-1 — 8gn-2 + n

Подсказка

Производящие функции — туда и обратно

Ответ

Производящие функции — туда и обратно

Заключение

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

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

Автор: timyrik20

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js