Главная > Математика > Конкретная математика. Основание информатики
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

6. Специальные числа

НЕКОТОРЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ чисел возникают в математике столь часто, что их узнают с первого взгляда и наделяют собственными названиями. Так, каждому изучающему арифметику известна последовательность квадратных чисел . В гл. 1 мы сталкивались с треугольными числами в гл. 4 занимались простыми числами а в гл. 5 промелькнули числа Каталана

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

6.1 ЧИСЛА СТИРЛИНГА

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

В табл. 288 и 289 показано, как выглядят числа при малых пик. Задача, которая включает в себя числа скорее всего должна быть связана с а задача, которая включает

Таблица 288 Треугольник Стирлинга для числа подмножеств.

в себя числа скорее всего с — точно так же, как мы предполагаем, что задача, которая включает в себя числа скорее всего должна быть связана с : это „фирменные знаки“ последовательностей, которые получаются при

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

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

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

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

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

Таблица 289 Треугольник Стирлинга для числа циклов.

остаться две непустые части. Поэтому вычтем 1:

(Это согласуется с приведенным выше перечислением способов разбиения:

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

Это именно то правило, в соответствии с которым образуется табл. 288; без множителя к оно свелось бы к формуле сложения (5.8), в соответствии с которой образуется треугольник Паскаля.

А теперь — числа Стирлинга первого рода. Эти числа отчасти похожи на числа второго рода с тем отличием, что подсчитывает число способов представления объектов в виде к циклов вместо представления в виде подмножеств. Вслух обозначение произносится как циклов из

Циклы — это циклические представления, аналогичные ожерельям, которые мы рассматривали в гл. 4. Цикл

можно записать более компактно как понимая при этом, что

цикл „прокручивается", поскольку его конец соединен с началом. С другой стороны, цикл — это не то же самое, что цикл или цикл

Существует одиннадцать различных способов составить два цикла из четырех элементов:

следовательно,

Единичный цикл (т. е. цикл, состоящий только из одного элемента) — это по существу то же самое, что и единичное множество (множество, состоящее только из одного элемента). Аналогично, -цикл подобен -множеству, поскольку , точно так же, как Однако существуют два различных -цикла: . Отметим, например, что одиннадцать пар циклов в (6.4) можно получить из семи пар множеств в (6.1), составив из каждого -элементного множества по два цикла.

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

Это значительно больше величины которая была получена для числа подмножеств Стирлинга. И в самом деле, легко убедиться в том, что число циклов должно быть по меньшей мере таким же, как и число подмножеств:

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

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

В самом деле, легко убедиться в том, что

(Число способов представления объектов в виде циклов или подмножеств равно числу способов выбора двух объектов, которые окажутся в одном и том же цикле или подмножестве.) Треугольные числа обращают на себя внимание как в табл. 288, так и в табл. 289.

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

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

Это аналог формулы сложения, с помощью которой образуется табл. 289.

Сравнение рекуррентностей (6.8) и (6.3) показывает, что первый член в их правых частях умножен на его верхний индекс в случае числа циклов Стирлинга, а в случае числа подмножеств Стирлинга — на его нижний индекс к. Поэтому, когда доказательство проводится с помощью математической индукции, можно осуществлять „внесение" в членах типа

Каждая перестановка эквивалентна некоторому множеству циклов. Рассмотрим, например, перестановку, которая переводит 123456789 в 384729156. Для наглядности ее можно представить в двух строках,

откуда видно, что 1 переходит в 3, 2 переходит в 8 и т. д. Возникает циклическая структура, ибо число 1 переходит в 3, которое переходит в 4, которое переходит в 7, которое переходит обратно в 1, т. е. это цикл [1,3,4,7]. Другим циклом в этой перестановке является [2,8,5], еще одним — [6,9]. Таким образом, перестановка 384729156 эквивалентна циклическому представлению

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

Следовательно, — это число перестановок объектов, которое содержит ровно к циклов. Если просуммировать по всем к, то мы должны получить общее число перестановок:

Так, .

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

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

И действительно, простое доказательство по индукции разрешает все сомнения: так как ; следовательно есть

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

Можно двигаться и в другом направлении, поскольку число циклов Стирлинга — это коэффициенты при обычных степенях, которые дают факториальные степени:

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

А это приводит к доказательству по индукции общей формулы:

(Подстановка вновь дает

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

Это оправданно, например, потому, что формула

почти такая же, что и формула

за исключением перемены знаков. Общее тождество

из упр. 2.17 превращает в (6.13), если изменить знак х.

(см. скан)

(см. скан)

Нетрудно запомнить, когда надо вставлять множитель в формулу типа (6.12), поскольку при большом х имеет место естественное упорядочение степеней:

А поскольку числа Стирлинга неотрицательны, знаки минус нужно использовать при выражении „малых" степеней через „большие"

Формулу можно подставить в (6.12) и получить двойную сумму:

Так как это справедливо при любом х, то все коэффициенты при в правой части должны быть равны нулю, и мы получаем тождество

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

Когда в гл. 5 мы изучали биномиальные коэффициенты, то установили, что выгодно определить и для отрицательного с тем, чтобы тождество выполнялось без каких-либо ограничений. Используя это тождество для распространения биномиальных коэффициентов за комбинаторные рамки, мы обнаружили (в табл. 189), что треугольник Паскаля, в сущности, воспроизводит себя в перевернутом виде при его продолжении вверх. Попробуем проделать то же самое с треугольниками Стирлинга. Что случится, если предположить, что основные рекуррентности

Таблица 297 Треугольники Стирлинга в тандеме.

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

В самом деле, вырисовывается удивительно приятная картина: треугольник Стирлинга для циклов появляется над треугольниками Стирлинга для подмножеств, и наоборот! Оба рода чисел Стирлинга связаны исключительно простым правилом [152, 153]:

Имеет место соотношение „двойственности" отчасти аналогичное соотношениям между min и max, между между между Легко проверить, что при таком соответствии оба рекуррентных соотношения сводятся к одному и тому же.

<< Предыдущий параграф Следующий параграф >>
Оглавление