|
|
Статьи Соросовского Образовательного журнала в текстовом формате
Приведены примеры производящих функций различных последовательностей, среди которых числа Фибоначчи, числа Каталана, числа Стирлинга.
ПРОИЗВОДЯЩИЕ ФУНКЦИИЕ. М. БРОНШТЕЙН
Уфимский государственный авиационный технический университет
ВВЕДЕНИЕ
В математике можно выделить два могучих направления: одно изучает непрерывные объекты, другое - дискретные. В реальном мире есть место и для того и для другого подхода и часто к изучению одного и того же явления можно подойти с разных точек зрения. Разумеется, между этими направлениями существует множество связей. Статья посвящена одной из них.
Идея производящей функции очень простая. Сопоставим последовательности a0 , a1 , _, an , _ (дискретному объекту) степенной ряд a0 + a1x + _ + anxn + _ (непрерывный объект). Поступив так, мы подключаем к изучению дискретных объектов мощный арсенал средств математического анализа. Заметим, что в рассмотренных ниже примерах степенные ряды сходятся на некоторой окрестности нуля, хотя существует теория формальных степенных рядов, которая рассматривает и степенные ряды, сходящиеся только в точке 0. Справедлива теорема единственности: если при некотором положительном "с" функция f (x) представима в виде степенного ряда a0 + + a1x + _ + anxn + _ на интервале (- с, с), то коэффициенты ai ряда определяются однозначно. Есть и иные конструкции производящих функций - одна из них затронута в конце статьи. Мы будем использовать известные из базового курса математического анализа свойства степенных рядов без дополнительных указаний. Некоторые свойства и применения степенных рядов приведены в [1].
Метод производящих функций очень продуктивен, в частности при решении комбинаторных задач. Приведем некоторые начальные примеры.
1. Самым известным примером производящей функции является, конечно, бином Ньютона
Здесь - биномиальные коэффициенты (число сочетаний из n по k, то есть число k-элементных подмножеств n-элементного множества).
2. Можно обобщить понятие биномиального коэффициента на случай, когда число n не является натуральным:
Соответствующая производящая функция - это уже не многочлен, как (1), а степенной ряд, сумма которого на промежутке (-1, 1) равна (1 + x)a, то есть справедливо равенство
При натуральных значениях a формула (2) превращается в (1).
3. Важные частные случаи формулы (2) получаем при a = -1, a = - 2.
(1 + х)-1 = 1 - х + х2 - х3 + _
Это, разумеется, формула суммы бесконечно убывающей геометрической прогрессии со знаменателем - х.
(1 + х)- 2 = 1 - 2х + 3х2 - 4х3 + _
Заменив в этой формуле х на - х, получаем, что производящей функцией последовательности 1, 2, 3, _ является функция (1 - х)- 2.
Приведем несколько более сложных примеров построения и использования производящих функций.
ЧИСЛА ФИБОНАЧЧИ
Числа Фибоначчи находят по следующему правилу: F0 = = F1 = 1, Fn = Fn - 1 + Fn - 2 при n > 1. Попытаемся получить формулу, выражающую значения Fn непосредственно через n. Один из путей к решению этой задачи - построение производящей функции. Пусть
Выделим в (3) два первых слагаемых, а в остальные подставим выражение Fn = Fn - 1 + Fn - 2 . Получим
Далее заметим, что
Используя эти равенства, получаем j(x) = 1 + x + + x(j(x) - 1) + x2j(x). Мы получили линейное уравнение относительно функции j(х). Решая его, находим
Обозначим через х1 и х2 корни квадратного трехчлена х2 + х - 1. Имеем
Тогда
Как известно, существуют такие числа А и В, для которых
Вычисления показывают, что
Преобразуя выражение для j(х), получаем
Здесь применены формула (2) при a = -1 и замена х в первом слагаемом на х / x1 , во втором - на х / x2 . По теореме единственности, приведенной во введении, из (3) и (5) следует равенство
Мы получили простую формулу для вычисления чисел Фибоначчи. Участие в ней иррационального числа выглядит неожиданно. При больших k слагаемое становится исчезающе малым, то есть справедливо приближенное равенство
Число - известное еще древним золотое сечение, то есть отношение, в котором надо разделить отрезок таким образом, чтобы отношение всего отрезка к большей части равнялось отношению большей части к меньшей.
Обратим внимание на то, как мы получили формулу (6): мы начали со степенного ряда (3), затем вроде о степенном ряде забыли (4), но только для того, чтобы снова вернуться к нему на новом уровне (5). Такой зигзаг и позволил получить эту красивую формулу.
СЧАСТЛИВЫЕ БИЛЕТЫ
Трамвайные билеты в доабонементную эпоху нумеровались шестизначными числами. Суеверные люди считали билет счастливым, если суммы первых трех и последних трех цифр совпадают. Мы здесь обсудим вопрос: сколько существует счастливых билетов?
Обозначим через uk (0 # k # 27) количество трехзначных чисел, сумма цифр которых равна k. Тогда существует счастливых билетов с суммой цифр 2k. Поэтому общее число счастливых билетов
Рассмотрим многочлен P(x) = (1 + x + x2 + _ + x9)3. Любому слагаемому, возникающему при раскрытии скобок, можно взаимно однозначно сопоставить трехзначное число. Например, произведению x3 " x6 " x2 (= x11) соответствует число 362. Отсюда видно, что uk есть коэффициент при xk многочлена P(x), то есть
Рассмотрим теперь функцию (функции такого типа иногда называют многочленами Лорана) Q(x) = P(x) i i P(1/ x). Если раскрыть скобки, то получим, что
При этом, как легко убедиться,
Следующий шаг является очень сильным. Неявно предполагалось, что рассматриваются функции вещественной переменной. Будем теперь считать, что функция Q зависит от комплексной переменной z. Это позволяет привлечь дополнительно средства комплексного анализа. В частности, к функции Q(z) можно применить интегральную формулу Коши, которая имеет вид
Здесь в качестве С можно принять произвольную окружность на комплексной плоскости, содержащую внутри точку 0 и проходимую против часовой стрелки. В частности, можно в качестве С взять единичную окружность с центром 0, точки которой представимы в виде z = eij, где j k [0, 2p], i - мнимая единица. В этом случае dz = ieij dj. Подставляя эти выражения в (7), получим
Упростим функцию Q(eij):
Q(eij) = P(eij)P(e- ij).
Учитывая, что
P(x) = (1 + x + x2 + _ + x9)3 =
имеем
Здесь использованы формула суммы геометрической прогрессии, формула Эйлера cos a = (eia + e- ia)/2 и формула косинуса двойного угла.
Окончательно получаем формулу
Наверное, заранее невозможно было представить, что число счастливых билетов можно свести к вычислению интеграла, да к тому же с привлечением средств комплексного анализа.
Число S можно вычислить и иначе. Пусть a1b1c1a2b2c2 - десятичная запись шестизначного числа А. Рассмотрим функцию, сопоставляющую числу А число, имеющее десятичную запись a1b1c1(9 - a2)(9 - b2)(9 - c2). Функция f (A ) является взаимно однозначной, причем f (A ) ? А и f ( f (A )) = А при всех А. Если число А счастливое, то a1 + b1 + c1 = a2 + b2 + c2 , откуда следует, что сумма цифр числа f (A ) равна 27. Обратно: если сумма цифр числа А равна 27, то число f (A ) счастливое. Отсюда следует, что S есть также количество шестизначных чисел, сумма цифр которых равна 27. Но тогда аналогично предыдущему S есть коэффициент многочлена
при x27.
Второй сомножитель можно представить в виде степенного ряда (2):
Отсюда видно, что коэффициент при x27 равен
Заметим, что
Отсюда получаем
Сравнение формул (8) и (9) показывает, например, что с помощью подобных соображений можно вычислять некоторые интегралы - еще одна неожиданность.
ЦИКЛЫ ПЕРЕСТАНОВОК
Перестановкой n-го порядка называется правило, которое каждому числу из множества {1, 2, _, n} сопоставляет одно из этих же чисел, причем разным числам сопоставляются разные числа. Теория перестановок - важнейший объект теории конечных групп и комбинаторики. Перестановка обычно записывается в виде строки, в которой на первом месте стоит число, сопоставленное единице, на втором - число, сопоставленное двойке, _, на n-м месте - число, сопоставленное n. Например, при n = 5 перестановка может иметь вид (5, 4, 1, 2, 3). Если проследить цепочки, которые порождает перестановка, получим 1-5-3-1, 2-4-2, то есть данная перестановка распадается на два цикла: один состоит из трех, другой - из двух чисел. Известно [2, 3], что любая перестановка распадается на циклы. Обозначим через C(n, k) число перестановок n-го порядка, имеющих k циклов. Эти числа называются числами Стирлинга первого рода (без знака).
Некоторые из чисел Стирлинга легко вычисляются. C(n, n) = 1, поскольку если число циклов равно n, то каждый цикл состоит из одного числа, то есть соответствующая перестановка имеет вид (1, 2, _, n). C(n, 0) = 0 при n > 0, поскольку, как уже отмечалось, всякая перестановка имеет хотя бы один цикл. Удобно считать, что C(0, 0) = 1.
Проверим справедливость равенства
C(n, k) = (n - 1)C(n - 1, k) + C(n - 1, k - 1)
при n, k $ 1, n $ k.
Для n, k = 1 это равенство проверяется непосредственно. Пусть перестановка (n - 1)-го порядка распадается на k циклов. Число n можно добавить после любого числа в соответствующий цикл. Все полученные перестановки различные, содержат k циклов, всего их (n - 1)C(n - 1, k). Далее из любой перестановки (n - 1)-го порядка, распадающейся на k - 1 цикл, можно сформировать единственную перестановку n порядка, распадающуюся на k циклов, добавив цикл, состоящий из одного числа n. Очевидно, что эта конструкция описывает все перестановки n-го порядка, распадающиеся на k циклов. Тем самым равенство (10) доказано.
Рассмотрим теперь производящую функцию
Fn(x) = C(n, 0) + C(n, 1)x + _ + C(n, n)xn.
Интересно, что, хотя нет простых формул для вычисления C(n, k), многочлен Fn(x) имеет весьма простую структуру:
Fn(x) = x(x + 1)_(x + n - 1).
Докажем эту формулу по индукции. Очевидно, что F1(x) = х. Пусть Fn(x) = x(x + 1)_(x + n - 1) при n $ 1. Имеем
Fn + 1(x) = C(n + 1, 0) + C(n + 1, 1)x + _
_ + C(n + 1, n + 1)xn + 1 = 0 + [nC(n, 1) + C(n, 0)]x + _
_ + [nC(n, n) + C(n, n - 1)]xn + xn + 1 =
= C(n, 1)(n + x)x + C(n, 2)(n + x)x2 + _
_ + C(n, n - 1)(n + x)xn + C(n, n)nxn + C(n, n)xn + 1 =
= (C(n, 0) + C(n, 1)x + _ + C(n, n)xn)(x + n) =
= x(x + 1)_(x + n),
что и требовалось проверить. Здесь использованы полученные ранее равенства C(n, 0) = 0, C(n, n) = 1.
В [4] приведены еще два доказательства замечательной формулы (12). Полученная производящая функция позволяет легко вычислять числа Стирлинга из (11), хотя, как уже отмечалось, простой формулы для этого не существует.
ЧИСЛА КАТАЛАНА
Последовательность Каталана не менее интересна, чем последовательность Фибоначчи, хотя и менее известна. Обе они возникают в самых разных задачах. Рассмотрим, в частности, задачу о правильной расстановке скобок. Обозначим через kп число способов, которыми можно правильно расставить n пар круглых скобок. Расстановка является правильной, если каждой открывающей скобке соответствует скобка закрывающая и наоборот.
Например, расстановка (( )( )) правильная, а расстановка ( ))( неправильная. Проверка правильности очень проста. Левее любой скобки число открывающих скобок должно быть не меньше, чем число скобок закрывающих. Числа kп и называются числами Каталана.
Очевидно, что k1 = 1, k2 = 2. Для общности следующей формулы полезно считать, что k0 = 1, то есть что при отсутствии скобок есть одна их правильная расстановка.
Пусть есть правильная расстановка n пар скобок. Первой открывающей скобке соответствует некоторая закрывающая. Между ними расположена правильная расстановка некоторого числа (пусть m) пар скобок. После отмеченной закрывающей скобки располагается правильная расстановка (n - m - 1) пар скобок. Соглашение k0 = 1 необходимо для того, чтобы это рассуждение было справедливо для любых m < n. Обратно если даны правильные расстановки m и n - m - 1 пар скобок при некотором m < n, то таким приемом получаем единственную расстановку n пар скобок. Отсюда следует рекуррентная формула
Пусть K(x) = k0 + k1x + k2x2 + _ - производящая функция последовательности Каталана. Тогда
Отсюда получаем квадратное уравнение относительно функции K(x):
xK 2(x) - K(x) + 1 = 0.
Решая его, получаем
Поскольку K(0) = 1, решением является функция
Разложив функцию в ряд по формуле (2), получаем
Эта формула интересна тем, что прямое доказательство того, что при любом n число делится на п + 1, не является простым.
ДОПОЛНИТЕЛЬНЫЕ ЗАМЕЧАНИЯ
1. Применение производящих функций позволяет доказать некоторые комбинаторные формулы, которые иначе получить очень трудно. Приведем пример такого рода. Разложение функции (1 - 4х)-1/2 в степенной ряд имеет вид Поэтому справедливо равенство
Приравнивая коэффициенты при xn в левой и правой частях, получаем
Эта формула имеет прозрачный комбинаторный смысл, но доказать ее непросто. Еще в 80-е годы XX века появлялись публикации, посвященные этому сюжету.
2. Понятие производящей функции, использованное выше, можно обобщить по-разному. Например, последовательность может зависеть не от одного, а от двух индексов cn, m . Разумеется, любую последовательность можно развернуть в линию, но это не всегда выглядит естественно. Такой последовательности можно сопоставить производящую функцию Например, для чисел такая функция имеет вид Преобразуем это выражение:
То есть, изучая последнюю функцию, мы можем исследовать свойства всех биномиальных коэффициентов сразу.
В заключение отметим, что многие другие примеры производящих функций можно найти в [4-6].
ЛИТЕРАТУРА
1. Сильвестров В.В. Степенные ряды и их приложения // Соросовский Образовательный Журнал. 1998. ╧ 10. С. 124-127.
2. Курош А.Г. Курс высшей алгебры. М.: Наука, 1968. 438 с.
3. Калужнин Л.А. Введение в общую алгебру. М.: Наука, 1973. 448 с.
4. Стенли Р. Перечислительная комбинаторика. М.: Мир, 1990. 440 с.
5. Ландо С.К. Комбинаторика. М.: Изд. Независимого моск. ун-та, 1994. 78 с.
6. Грэхем Р., Кнут Д., Паташник О. Конкретная математика. М.: Мир, 1998. 704 с.
Рецензент статьи Ю.П. Соловьев
* * *
Ефим Михайлович Бронштейн, доктор физико-математических наук, профессор кафедры вычислительной математики и кибернетики Уфимского государственного авиационного технического университета, Соросовский доцент (1995, 1998, 1999 годы). Область научных интересов - выпуклый анализ, дискретная математика, финансовая математика. Автор почти 100 научных публикаций и учебных пособий.
