«Производящая функция является устройством, отчасти напоминающим мешок. Вместо того чтобы нести отдельно много предметов, что могло бы оказаться затруднительным, мы собираем их вместе, и тогда нам нужно нести лишь один предмет — мешок».
Введение
Математика делится на два мира — дискретный и непрерывный. В реальном мире есть место и для того и для другого, и часто к изучению одного явления можно подойти с разных сторон. В этой статье мы рассмотрим метод решения задач с помощью производящих функций — мостика ведущего из дискретного мира в непрерывный, и наоборот.
Идея производящих функций достаточно проста: сопоставим некоторой последовательности <g0, g1, g2, ..., gn> — дискретному объекту, степенной ряд g0 + g1z + g2z2 +… + gnzn +… — объект непрерывный, тем самым мы подключаем к решению задачи целый арсенал средств математического анализа. Обычно говорят, последовательность генерируется, порождается производящей функцией. Важно понимать, что это символьная конструкция, то есть вместо символа z может быть любой объект, для которого определены операции сложения и умножения.
История возникновения производящих функций
Известно, что начало методу производящих функций положил английский математик Абрахам де Муавр, а дальнейшему развитию и продолжению данного метода мы обязаны великому математику, имя которого Леонард Эйлер.
В 50-х годах XVIII века Эйлер решал следующую задачу: какие грузы можно взвесить с помощью гирь в 20, 21, 22,..., 2n грамм и сколькими способами? При решении этой задачи он использовал никому неизвестный на то время метод производящих функций, которому и посвящена данная статья. К этой задаче мы вернёмся немного позже, после того как разберёмся более подробно с устройством производящих функций.
Изучение этого мощного механизма позволяющего решать многие задачи, мы начнём с простенькой задачи: сколькими способами можно расположить в линию чёрные и белые шары, общее количество которых равно n?
Обозначим белый шар символом ○, чёрный — ●, Tn — искомое количество расположений шаров. Символом Ø — обозначим нулевое количество шаров. Как и любое решение комбинаторной задачи начнём с тривиальных случаев:
Если 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 = Ø + ○G +●G.
Несмотря на то, что умножение некоммутативно, и мы фактически не различаем левое и правое деление, попробуем всё же «решить» это уравнение, на свой страх и риск. Получим,
Учитывая формулу суммы геометрической прогрессии
, имеем
.
В этой сумме так же учтены все возможные варианты разбиения в точности по одному разу. Далее воспользуемся формулой бинома Ньютона:
, где 
— число сочетаний из n по k. Тогда с учетом этого имеем:
Коэффициент при ○k ●n-k равный числу сочетаний из n по k, показывает общее количество последовательностей из n шаров содержащих ○ шары в количеств 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)… которое после раскрытия скобок представляется в виде бесконечного ряда G(z) = 1 + g1z + g2z2 + g3z3 +….
Что же из себя представляют коэффициенты gk? Каждый gk — это коэффициент при zk, а zk — получается как произведение каких-то одночленов z2m, то есть gk — это в точности число разных представлений числа k в виде суммы некоторых из чисел 1, 2, 22, 23,..., 2m,…. Другими словами gk — это число способов взвешивания груза в k грамм заданными гирями. Как раз то, что мы искали!
Следующий шаг Эйлера поражает не менее предыдущего. Он умножает обе части равенства на (1-z).
(1-z)G(z) = (1-z)(1+z)(1+z2)(1+z4)(1+z8)…
(1-z)G(z) = (1-z2)(1+z2)(1+z4)(1+z8)…
(1-z)G(z) = (1-z4)(1+z4)(1+z8)…
(1-z)G(z) = 1
С одной стороны G(z) = 1 + g1z + g2z2 + g3z3 +… с другой стороны мы только что получили. Последнее равенство есть не что иное, как сумма геометрической прогрессии, которая равна 
. Сопоставляя эти два равенства, получаем 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) = z + z G(z) + z2 G(z) решая которое относительно G(z) находим
— производящая функция для последовательности чисел Фибоначчи.
Разложим её на сумму простейших дробей, для этого найдем корни уравнения
. Решая это простое квадратное уравнение, получаем: 
. Тогда нашу производящую функцию можно разложить следующим образом:
Следующим шагом является нахождение коэффициентов a и b. Для этого умножим дроби на общий знаменатель:
Подставляя в это уравнение значение z = z1 и z = z2, находим
Напоследок немного преобразуем выражение для производящей функции
Теперь каждая из дробей представляет собой сумму геометрической прогрессии.
По формуле
находим 
Но ведь мы искали G(z) в виде
. Отсюда делаем вывод, что
Эту формулу можно переписать в другом виде не используя «золотое сечение»:
что достаточно трудно было ожидать, учитывая красивое рекуррентное уравнение.
Давайте запишем общий алгоритм решения рекуррентных уравнений, используя производящие функции. Он записывается в 4 шага:
Причина, по которой данный метод работает, заключается в том, что единая функция G(z) представляет всю последовательность gn и это представление допускает многие преобразования.
Прежде чем переходить к следующему примеру, рассмотрим 2 операции, совершаемые над производящими функциями, которые часто оказываются полезными.
Для производящих функций обычное определение производной можно записать следующим образом.
Пусть G = G(z) – производящая функция. Производной этой функции называется функция
. Дифференцирование, очевидно, линейная операция, поэтому для того, чтобы понять, как оно действует на производящих функциях, достаточно посмотреть на его действие, на степенях переменной. Имеем
Тем самым, действие дифференцирования на произвольной производящей функции
G (z) = g0 + g1z + g2z2 + g3z3 +… дает G΄(z) = g1 + 2g2z + 3g3z2 + 4g4z3 +….
Интегралом называется функция
Операция дифференцирования обратна операции интегрирования:
Операция же интегрирования производной приводит к функции с нулевым свободным членом, и поэтому результат, отличается от исходной функции,
Нетрудно заметить, что для функций, представимых в виде степенных рядов, формула для производной соответствует обычной. Формула для интеграла соответствует значению интеграла с переменным верхним пределом
Используя только что полученные знания о дифференцировании и интегрировании производящих функций, попробуем решить следующее рекуррентное уравнение:
g0 = 1,
g1 = 1,
gn = gn-1 + 2gn-2 + (-1)n
По первым значениям n трудно сказать что-либо об общей формуле:
Будем следовать вышеописанному алгоритму. Первое условие алгоритма выполнено. Умножим обе части всех равенств на z в соответствующей степени и просуммируем:
z0⋅ g0 = 1,
z1 ⋅ g1 = z,
zn ⋅ gn = zn ⋅ gn-1 + 2zn ⋅ gn-2 + (-1)n ⋅ zn
Левая часть
представляет собой производящую функцию в бесконечном виде.
Попытаемся выразить правую часть через G(z). Рассмотрим каждое слагаемое:
Составляем уравнение:
Это и есть производящая функция для заданного рекуррентного уравнения. Раскладывая её на простейшие дроби (например, методом неопределенных коэффициентов или методом подстановки различных значений z), получаем:
Второе и третье слагаемые легко раскладываются в степенной ряд, а вот с первым придется чуть повозиться. Используя правило дифференцирования производящих функций имеем:
Собственно всё. Раскладываем каждое слагаемое в степенной ряд и получаем ответ:
С одной стороны мы искали G(z) в виде
, с другой стороны 
.
Значит,
.
Производящие функции нашли большое применение в математике, поскольку являются мощным оружием при решении многих практических задач, связанных, например, с перечислением, распределением и разбиением множеств объектов различной природы. Кроме того применение производящих функций позволяет доказать некоторые комбинаторные формулы, которые иначе получить очень трудно. Например, разложение функции
в степенной ряд имеет вид 
, то есть справедливо равенство:
Возводя в квадрат обе части этого равенства получим
Приравнивая коэффициенты при xn в левой и правой частях, получаем
Эта формула имеет прозрачный комбинаторный смысл, но доказать её непросто. Еще в 80-е годы XX века появились публикации, посвященный этому вопросу.
Д. Пойа
Введение
Математика делится на два мира — дискретный и непрерывный. В реальном мире есть место и для того и для другого, и часто к изучению одного явления можно подойти с разных сторон. В этой статье мы рассмотрим метод решения задач с помощью производящих функций — мостика ведущего из дискретного мира в непрерывный, и наоборот.
Идея производящих функций достаточно проста: сопоставим некоторой последовательности <g0, g1, g2, ..., gn> — дискретному объекту, степенной ряд g0 + g1z + g2z2 +… + gnzn +… — объект непрерывный, тем самым мы подключаем к решению задачи целый арсенал средств математического анализа. Обычно говорят, последовательность генерируется, порождается производящей функцией. Важно понимать, что это символьная конструкция, то есть вместо символа z может быть любой объект, для которого определены операции сложения и умножения.
История возникновения производящих функций
Известно, что начало методу производящих функций положил английский математик Абрахам де Муавр, а дальнейшему развитию и продолжению данного метода мы обязаны великому математику, имя которого Леонард Эйлер.
В 50-х годах XVIII века Эйлер решал следующую задачу: какие грузы можно взвесить с помощью гирь в 20, 21, 22,..., 2n грамм и сколькими способами? При решении этой задачи он использовал никому неизвестный на то время метод производящих функций, которому и посвящена данная статья. К этой задаче мы вернёмся немного позже, после того как разберёмся более подробно с устройством производящих функций.
Метод производящих функций
Изучение этого мощного механизма позволяющего решать многие задачи, мы начнём с простенькой задачи: сколькими способами можно расположить в линию чёрные и белые шары, общее количество которых равно n?
Обозначим белый шар символом ○, чёрный — ●, Tn — искомое количество расположений шаров. Символом Ø — обозначим нулевое количество шаров. Как и любое решение комбинаторной задачи начнём с тривиальных случаев:
Если 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 = Ø + ○G +●G.
Несмотря на то, что умножение некоммутативно, и мы фактически не различаем левое и правое деление, попробуем всё же «решить» это уравнение, на свой страх и риск. Получим,
Учитывая формулу суммы геометрической прогрессии
, имеем .В этой сумме так же учтены все возможные варианты разбиения в точности по одному разу. Далее воспользуемся формулой бинома Ньютона:
, где — число сочетаний из n по k. Тогда с учетом этого имеем: Коэффициент при ○k ●n-k равный числу сочетаний из n по k, показывает общее количество последовательностей из n шаров содержащих ○ шары в количеств 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)… которое после раскрытия скобок представляется в виде бесконечного ряда G(z) = 1 + g1z + g2z2 + g3z3 +….
Что же из себя представляют коэффициенты gk? Каждый gk — это коэффициент при zk, а zk — получается как произведение каких-то одночленов z2m, то есть gk — это в точности число разных представлений числа k в виде суммы некоторых из чисел 1, 2, 22, 23,..., 2m,…. Другими словами gk — это число способов взвешивания груза в k грамм заданными гирями. Как раз то, что мы искали!
Следующий шаг Эйлера поражает не менее предыдущего. Он умножает обе части равенства на (1-z).
(1-z)G(z) = (1-z)(1+z)(1+z2)(1+z4)(1+z8)…
(1-z)G(z) = (1-z2)(1+z2)(1+z4)(1+z8)…
(1-z)G(z) = (1-z4)(1+z4)(1+z8)…
(1-z)G(z) = 1
С одной стороны G(z) = 1 + g1z + g2z2 + g3z3 +… с другой стороны мы только что получили
. Последнее равенство есть не что иное, как сумма геометрической прогрессии, которая равна . Сопоставляя эти два равенства, получаем 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) = z + z G(z) + z2 G(z) решая которое относительно G(z) находим
— производящая функция для последовательности чисел Фибоначчи. Разложим её на сумму простейших дробей, для этого найдем корни уравнения
. Решая это простое квадратное уравнение, получаем: . Тогда нашу производящую функцию можно разложить следующим образом: Следующим шагом является нахождение коэффициентов a и b. Для этого умножим дроби на общий знаменатель:
Подставляя в это уравнение значение z = z1 и z = z2, находим
Напоследок немного преобразуем выражение для производящей функции
Теперь каждая из дробей представляет собой сумму геометрической прогрессии.
По формуле
находим Но ведь мы искали G(z) в виде
. Отсюда делаем вывод, чтоЭту формулу можно переписать в другом виде не используя «золотое сечение»:
что достаточно трудно было ожидать, учитывая красивое рекуррентное уравнение.
Давайте запишем общий алгоритм решения рекуррентных уравнений, используя производящие функции. Он записывается в 4 шага:
- Запишите одно уравнение, выражающее gn через другие элементы последовательности. Это уравнение должно оставаться справедливым для всех целых n с учетом того, что g-1=g-2=....=0.
- Умножьте обе части уравнения на zn и просуммируйте по всем n. В левой части получится сумма
, которая равна производящей функции G(z). Правую часть следует преобразовать так, чтобы она превратилась в какое-то другое выражение, включающее G(z). - Решите полученное уравнение, получив для G(z) выражение в замкнутом виде.
- Разложите G(z) в степенной ряд и прочитайте коэффициент при zn, это и будет замкнутый вид для gn.
Причина, по которой данный метод работает, заключается в том, что единая функция G(z) представляет всю последовательность gn и это представление допускает многие преобразования.
Прежде чем переходить к следующему примеру, рассмотрим 2 операции, совершаемые над производящими функциями, которые часто оказываются полезными.
Дифференцирование и интегрирование производящих функций
Для производящих функций обычное определение производной можно записать следующим образом.
Пусть G = G(z) – производящая функция. Производной этой функции называется функция
. Дифференцирование, очевидно, линейная операция, поэтому для того, чтобы понять, как оно действует на производящих функциях, достаточно посмотреть на его действие, на степенях переменной. ИмеемТем самым, действие дифференцирования на произвольной производящей функции
G (z) = g0 + g1z + g2z2 + g3z3 +… дает G΄(z) = g1 + 2g2z + 3g3z2 + 4g4z3 +….
Интегралом называется функция
Операция дифференцирования обратна операции интегрирования:
Операция же интегрирования производной приводит к функции с нулевым свободным членом, и поэтому результат, отличается от исходной функции,
Нетрудно заметить, что для функций, представимых в виде степенных рядов, формула для производной соответствует обычной. Формула для интеграла соответствует значению интеграла с переменным верхним пределом
Используя только что полученные знания о дифференцировании и интегрировании производящих функций, попробуем решить следующее рекуррентное уравнение:
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,
z1 ⋅ g1 = z,
zn ⋅ gn = zn ⋅ gn-1 + 2zn ⋅ gn-2 + (-1)n ⋅ zn
Левая часть
представляет собой производящую функцию в бесконечном виде.Попытаемся выразить правую часть через G(z). Рассмотрим каждое слагаемое:
Составляем уравнение:
Это и есть производящая функция для заданного рекуррентного уравнения. Раскладывая её на простейшие дроби (например, методом неопределенных коэффициентов или методом подстановки различных значений z), получаем:
Второе и третье слагаемые легко раскладываются в степенной ряд, а вот с первым придется чуть повозиться. Используя правило дифференцирования производящих функций имеем:
Собственно всё. Раскладываем каждое слагаемое в степенной ряд и получаем ответ:
С одной стороны мы искали G(z) в виде
, с другой стороны . Значит,
.Вместо заключения
Производящие функции нашли большое применение в математике, поскольку являются мощным оружием при решении многих практических задач, связанных, например, с перечислением, распределением и разбиением множеств объектов различной природы. Кроме того применение производящих функций позволяет доказать некоторые комбинаторные формулы, которые иначе получить очень трудно. Например, разложение функции
в степенной ряд имеет вид , то есть справедливо равенство:Возводя в квадрат обе части этого равенства получим
Приравнивая коэффициенты при xn в левой и правой частях, получаем
Эта формула имеет прозрачный комбинаторный смысл, но доказать её непросто. Еще в 80-е годы XX века появились публикации, посвященный этому вопросу.
Комментариев нет:
Отправить комментарий