WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 |
МАТ Е МАТ ИКА МАТ Е МАТ ИКА ПРОИЗВОДЯЩИЕ ФУНКЦИИ Е. М. БРОНШТЕЙН Уфимский государственный авиационный технический университет ВВЕДЕНИЕ В математике можно выделить два могучих направлеGENERATING FUNCTIONS ния: одно изучает непрерывные объекты, другое – дисE. M. BRONSHTEIN кретные. В реальном мире есть место и для того и для другого подхода и часто к изучению одного и того же явления можно подойти с разных точек зрения. РазуThe examples of generating functions of меется, между этими направлениями существует мноvarious sequences are given, including жество связей. Статья посвящена одной из них.

Fibonacci, Katalan and Stirling numbers.

Идея производящей функции очень простая. Сопоставим последовательности a0, a1, …, an, … (дискретному Приведены примеры производящих функций объекту) степенной ряд a0 + a1x + … + anxn + … (непреразличных последовательностей, среди корывный объект). Поступив так, мы подключаем к изучеторых числа Фибоначчи, числа Каталана, нию дискретных объектов мощный арсенал средств математического анализа. Заметим, что в рассмотренных числа Стирлинга.

ниже примерах степенные ряды сходятся на некоторой окрестности нуля, хотя существует теория формальных степенных рядов, которая рассматривает и степенные ряды, сходящиеся только в точке 0. Справедлива теорема единственности: если при некотором положительном “с” функция f(x) представима в виде степенного ряда a0 + + a1x + … + anxn + … на интервале (- с, с), то коэффициенты ai ряда определяются однозначно. Есть и иные конструкции производящих функций – одна из них затронута в конце статьи. Мы будем использовать известные из базового курса математического анализа свойства степенных рядов без дополнительных указаний.

Некоторые свойства и применения степенных рядов приведены в [1].

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

1. Самым известным примером производящей функции является, конечно, бином Ньютона n n n n + x + … + xk + … + xn = (1 + x)n. (1) 0 1 k n n n! Здесь = ----------------------- – биномиальные коэффициенты k k!(n – k)! www.issep.rssi.ru (число сочетаний из n по k, то есть число k-элементных подмножеств n-элементного множества).

БРОНШТЕЙН Е.М. ПРОИЗВОДЯЩИЕ ФУНКЦИИ Бронштейн Е.М., © МАТ Е МАТ ИКА 2. Можно обобщить понятие биномиального коэфFk – 1xk – 1 = (x) – 1, Fk – 2xk – 2 = (x).

фициента на случай, когда число n не является нату- k = 2 k = ральным:

Используя эти равенства, получаем (x) = 1 + x + = ( – 1) … ( – k + 1) + x( (x) - 1) + x2 (x). Мы получили линейное уравне-------------------------------------------------------------------.

k! k ние относительно функции (х). Решая его, находим Соответствующая производящая функция – это уже не (x) = ----------------------. (4) многочлен, как (1), а степенной ряд, сумма которого на 1 – x – xпромежутке (- 1, 1) равна (1 + x)a, то есть справедливо равенство Обозначим через х1 и х2 корни квадратного трехчлена х2 + х - 1. Имеем + x + … + xk + … = (1 + x). (2) 5 + 1 5 – 1.

0 1 k x1 = –----------------, x2 = --------------2 При натуральных значениях формула (2) превраТогда щается в (1).

3. Важные частные случаи формулы (2) получаем (x) = –-------------------------------------.

при = - 1, = - 2.

(x – x1)(x – x2) (1 + х)- 1 = 1 - х + х2 - х3 + … Как известно, существуют такие числа А и В, для которых Это, разумеется, формула суммы бесконечно убывающей геометрической прогрессии со знаменателем - х.

A B (x) = ------------- + -------------.

x – x1 x – x(1 + х)- 2 = 1 - 2х + 3х2 - 4х3 + … Заменив в этой формуле х на - х, получаем, что про- Вычисления показывают, что изводящей функцией последовательности 1, 2, 3, … яв1-, 1ляется функция (1 - х)- 2.

A = –------ B = ------.

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

Преобразуя выражение для (х), получаем –1 –ЧИСЛА ФИБОНАЧЧИ A x B x (x) = –---- 1 – ---- – ---- 1 – ---- = x1 x1 x2 xЧисла Фибоначчи находят по следующему правилу: F0 = (5) = F1 = 1, Fn = Fn - 1 + Fn - 2 при n > 1. Попытаемся получить k k A x B x = –---- ---- – ---- ----.

формулу, выражающую значения Fn непосредственно x1 x1 x2 xk = 0 k = через n. Один из путей к решению этой задачи – построение производящей функции. Пусть Здесь применены формула (2) при = - 1 и замена х в первом слагаемом на х/x1, во втором – на х/x2. По теореме единственности, приведенной во введении, из (3) (x) = Fkxk. (3) и (5) следует равенство k = Выделим в (3) два первых слагаемых, а в остальные A B Fk = –----------------1 – ----------------1 = - подставим выражение Fn = Fn - 1 + Fn - 2. Получим (x1)k + (x2)k + (6) k + 1 k + 1- 5 + 1 1 – = ------ ---------------- – ---------------.

(x) = F0 + F1x + (Fk – 1 + Fk – 2)xk = 2 k = Мы получили простую формулу для вычисления = 1 + x + Fk – 1xk + Fk – 2xk = чисел Фибоначчи. Участие в ней иррационального k = 2 k = числа 5 выглядит неожиданно. При больших k слага k + = 1 + x + x Fk – 1xk – 1 + x2 Fk – 2xk – 2.

1- 1 – емое –------ --------------- становится исчезающе малым, то k = 2 k = 5 Далее заметим, что есть справедливо приближенное равенство СОРОСОВСКИЙ ОБРАЗОВАТЕЛЬНЫЙ ЖУРНАЛ, ТОМ 7, №2, МАТ Е МАТ ИКА k + воляет привлечь дополнительно средства комплексного 1- 1 + Fk ------ ----------------.

анализа. В частности, к функции Q(z) можно приме5 нить интегральную формулу Коши, которая имеет вид 1 Q(z)dz.

---------------Число 1 + 5 – известное еще древним золотое сеS = q0 = ---------- ----------- (7) 2 ii z ° C чение, то есть отношение, в котором надо разделить отЗдесь в качестве С можно принять произвольную окрезок таким образом, чтобы отношение всего отрезка к ружность на комплексной плоскости, содержащую большей части равнялось отношению большей части к внутри точку 0 и проходимую против часовой стрелки.



меньшей.

В частности, можно в качестве С взять единичную окОбратим внимание на то, как мы получили формуружность с центром 0, точки которой представимы в лу (6): мы начали со степенного ряда (3), затем вроде о виде z = ei, где [0, 2 ], i – мнимая единица. В этом степенном ряде забыли (4), но только для того, чтобы случае dz = iei d. Подставляя эти выражения в (7), поснова вернуться к нему на новом уровне (5). Такой зиглучим заг и позволил получить эту красивую формулу.

СЧАСТЛИВЫЕ БИЛЕТЫ S = ------ Q(ei )d.

Трамвайные билеты в доабонементную эпоху нумерова- лись шестизначными числами. Суеверные люди считаУпростим функцию Q(ei ):

ли билет счастливым, если суммы первых трех и последQ(ei ) = P(ei )P(e- i ).

них трех цифр совпадают. Мы здесь обсудим вопрос:

сколько существует счастливых билетов Учитывая, что Обозначим через uk (0 k 27) количество трехзначных чисел, сумма цифр которых равна k. Тогда су--------------P(x) = (1 + x + x2 + … + x9)3 = 1 – x10, 1 – x ществует u2 счастливых билетов с суммой цифр 2k. Поk этому общее число счастливых билетов имеем S = u2. -------------------------------------------------) Q(ei ) = (1 – e10i )(1 – e–10i - = k (1 – ei )(1 – e–i ) k = 3 3 Рассмотрим многочлен P(x) = (1 + x + x2 + … + x9)3.

------------------------------------ --------------------------- sin= 2 – e10i – e–10i = 1 – cos10- = -----------------------.

1 – cos sin( 2) Любому слагаемому, возникающему при раскрытии ско- 2 – ei – e–i бок, можно взаимно однозначно сопоставить трехзначЗдесь использованы формула суммы геометрической ное число. Например, произведению x3 x6 x2 (= x11) сопрогрессии, формула Эйлера cos = (ei + e- i )/2 и форответствует число 362. Отсюда видно, что uk есть мула косинуса двойного угла.

коэффициент при xk многочлена P(x), то есть Окончательно получаем формулу P(x) = ukxk.

1 sin S = ------ ----------------------- d. (8) k = 2 sin( 2) Рассмотрим теперь функцию (функции такого типа Наверное, заранее невозможно было представить, иногда называют многочленами Лорана) Q(x) = P(x) что число счастливых билетов можно свести к вычис P(1/x). Если раскрыть скобки, то получим, что лению интеграла, да к тому же с привлечением средств комплексного анализа.

Q(x) = qkxk.

Число S можно вычислить и иначе. Пусть k = –a1b1c1a2b2c2 – десятичная запись шестизначного числа А.

Рассмотрим функцию, сопоставляющую числу А число, При этом, как легко убедиться, q0 = u2 = S.

имеющее десятичную запись a1b1c1(9 - a2)(9 - b2)(9 - c2).

k k = Функция f (A) является взаимно однозначной, причем Следующий шаг является очень сильным. Неявно f(A) А и f(f(A)) = А при всех А. Если число А счастлипредполагалось, что рассматриваются функции веще- вое, то a1 + b1 + c1 = a2 + b2 + c2, откуда следует, что сумственной переменной. Будем теперь считать, что функ- ма цифр числа f(A) равна 27. Обратно: если сумма цифр ция Q зависит от комплексной переменной z. Это поз- числа А равна 27, то число f(A) счастливое. Отсюда БРОНШТЕЙН Е.М. ПРОИЗВОДЯЩИЕ ФУНКЦИИ МАТ Е МАТ ИКА следует, что S есть также количество шестизначных чи- Некоторые из чисел Стирлинга легко вычисляютсел, сумма цифр которых равна 27. Но тогда аналогич- ся. C(n, n) = 1, поскольку если число циклов равно n, то но предыдущему S есть коэффициент многочлена каждый цикл состоит из одного числа, то есть соответствующая перестановка имеет вид (1, 2, …, n). C(n, 0) = 6 – x10 6 при n > 0, поскольку, как уже отмечалось, всякая пере (1 + x + … + x9) = --------------- = (1 – x10) (1 – x)– 1 – x становка имеет хотя бы один цикл. Удобно считать, что C(0, 0) = 1.

при x27.

Проверим справедливость равенства Второй сомножитель можно представить в виде степенного ряда (2):

C(n, k) = (n - 1)C(n - 1, k) + C(n - 1, k - 1) (10) –при n, k 1, n k.

(1 – x)–6 = (–x)k.

k k = Для n, k = 1 это равенство проверяется непосредственно. Пусть перестановка (n - 1)-го порядка распадается Отсюда видно, что коэффициент при x27 равен на k циклов. Число n можно добавить после любого –6 6 –6 6 –6 числа в соответствующий цикл. Все полученные пе – + –.

рестановки различные, содержат k циклов, всего их 27 1 17 2 (n - 1)C(n - 1, k). Далее из любой перестановки (n - 1)-го Заметим, что порядка, распадающейся на k - 1 цикл, можно сформировать единственную перестановку n порядка, распа– дающуюся на k циклов, добавив цикл, состоящий из ----------------------------------------------------------- = (–1)k(k + 5)… = (–6)(–7)…(– 6 – k + 1) -------------------------- = k! k! k одного числа n. Очевидно, что эта конструкция описыk + 5 вает все перестановки n-го порядка, распадающиеся на ------------------ = (–1)k = (–1)k(k + 5)!.

k циклов. Тем самым равенство (10) доказано.

k!5! Рассмотрим теперь производящую функцию Отсюда получаем Fn(x) = C(n, 0) + C(n, 1)x + … + C(n, n)xn. (11) 32 6 22 6 S = – +. (9) 5 1 5 2 Интересно, что, хотя нет простых формул для вычисления C(n, k), многочлен Fn(x) имеет весьма простую Сравнение формул (8) и (9) показывает, например, что структуру:

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

Fn(x) = x(x + 1)…(x + n - 1). (12) ЦИКЛЫ ПЕРЕСТАНОВОК Докажем эту формулу по индукции. Очевидно, что F1(x) = х. Пусть Fn(x) = x(x + 1)…(x + n - 1) при n 1.





Перестановкой n-го порядка называется правило, котоИмеем рое каждому числу из множества {1, 2, …, n} сопоставляет одно из этих же чисел, причем разным числам со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) = ное двойке, …, на n-м месте – число, сопоставленное n.

= x(x + 1)…(x + n), Например, при n = 5 перестановка может иметь вид (5, 4, 1, 2, 3). Если проследить цепочки, которые почто и требовалось проверить. Здесь использованы порождает перестановка, получим 1–5–3–1, 2–4–2, то лученные ранее равенства C(n, 0) = 0, C(n, n) = 1.

есть данная перестановка распадается на два цикла:

один состоит из трех, другой – из двух чисел. Известно В [4] приведены еще два доказательства замеча[2, 3], что любая перестановка распадается на циклы. тельной формулы (12). Полученная производящая функОбозначим через C(n, k) число перестановок n-го по- ция позволяет легко вычислять числа Стирлинга из (11), рядка, имеющих k циклов. Эти числа называются чис- хотя, как уже отмечалось, простой формулы для этого лами Стирлинга первого рода (без знака). не существует.

СОРОСОВСКИЙ ОБРАЗОВАТЕЛЬНЫЙ ЖУРНАЛ, ТОМ 7, №2, МАТ Е МАТ ИКА ЧИСЛА КАТАЛАНА ----------------------------.

K(x) = 1 ± 1 – 4x 2x Последовательность Каталана не менее интересна, чем последовательность Фибоначчи, хотя и менее известна.

Поскольку K(0) = 1, решением является функция Обе они возникают в самых разных задачах. Рассмот1 – 1 – 4x рим, в частности, задачу о правильной расстановке ----------------------------.

2x скобок. Обозначим через kп число способов, которыми можно правильно расставить n пар круглых скобок.

Разложив функцию 1 – 4x в ряд по формуле (2), Расстановка является правильной, если каждой открыполучаем вающей скобке соответствует скобка закрывающая и наоборот.

n 2n (2n)! ------------------------------------------------------- kn = 2 1 3 … (2n – 1) = ------------------------ = -----------.

Например, расстановка (( )( )) правильная, а рас(n + 1)! n!(n + 1)! n + 1 n становка ( ))( неправильная. Проверка правильности Эта формула интересна тем, что прямое доказательство очень проста. Левее любой скобки число открывающих скобок должно быть не меньше, чем число скобок за2n того, что при любом n число делится на п + 1, не крывающих. Числа kп и называются числами Каталана.

n Очевидно, что k1 = 1, k2 = 2. Для общности следуюявляется простым.

щей формулы полезно считать, что k0 = 1, то есть что при отсутствии скобок есть одна их правильная расста- ДОПОЛНИТЕЛЬНЫЕ ЗАМЕЧАНИЯ новка.

1. Применение производящих функций позволяет доПусть есть правильная расстановка n пар скобок.

казать некоторые комбинаторные формулы, которые Первой открывающей скобке соответствует некоторая иначе получить очень трудно. Приведем пример такого закрывающая. Между ними расположена правильная рода. Разложение функции (1 - 4х)- 1/2 в степенной ряд расстановка некоторого числа (пусть m) пар скобок.

2n После отмеченной закрывающей скобки располагается имеет вид xn. Поэтому справедливо равенство n правильная расстановка (n - m - 1) пар скобок. Соглаn = шение k0 = 1 необходимо для того, чтобы это рассужде ние было справедливо для любых m < n. Обратно если 2n 2n (1 – 4x)–1 = xn xn.

даны правильные расстановки m и n - m - 1 пар скобок n n = 0 n n = при некотором m < n, то таким приемом получаем единственную расстановку n пар скобок. Отсюда сле- Приравнивая коэффициенты при xn в левой и правой дует рекуррентная формула частях, получаем n n – 2i 2(n – i) 4n =.

kn = kmkn – m – 1. (13) i n – i i = m = Эта формула имеет прозрачный комбинаторный Пусть K(x) = k0 + k1x + k2x2 + … – производящая смысл, но доказать ее непросто. Еще в 80-е годы XX века функция последовательности Каталана. Тогда появлялись публикации, посвященные этому сюжету.

2. Понятие производящей функции, использованK2(x) = (k0 + k1x + k2x2 + …)(k0 + k1x + k2x2 + …) = ное выше, можно обобщить по-разному. Например, m – последовательность может зависеть не от одного, а от = k2 + (k0k1 + k1k0)x + … + kmkn – m – 1xn – 1 + … = двух индексов cn, m. Разумеется, любую последовательm = ность можно развернуть в линию, но это не всегда вы= 1 + k2x + … + knxn – 1 + … = глядит естественно. Такой последовательности можно K(x) – k0 – k1x – 1.

K(x) = 1 + ------------------------------------- = --------------------сопоставить производящую функцию cn, mxnym. На x x n, m Отсюда получаем квадратное уравнение относительно n пример, для чисел такая функция имеет вид функции K(x):

m n xK2(x) - K(x) + 1 = 0.

n xmyn. Преобразуем это выражение:

m Решая его, получаем n = 0 m = БРОНШТЕЙН Е.М. ПРОИЗВОДЯЩИЕ ФУНКЦИИ МАТ Е МАТ ИКА n n 4. Стенли Р. Перечислительная комбинаторика. М.: Мир, n n xmyn = yn xm = yn(1 + x)n = 1990. 440 с.

m n = 0 m = 0 m n = n = 0 m = 5. Ландо С.К. Комбинаторика. М.: Изд. Независимого моск.

ун-та, 1994. 78 с.

= -----------------------------.

1 – y(1 + x) 6. Грэхем Р., Кнут Д., Паташник О. Конкретная математика.

М.: Мир, 1998. 704 с.

Pages:     || 2 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.