Замечательные комбинаторные числа

МИНИСТЕСТЕРСТВО

 

 

Оглавление

ВВЕДЕНИЕ 3

1 ЧИСЛА КАТАЛАНА 4

1.1 Разрезание треугольников. 4

1.2 Вычисление произведений. 6

1.3 Расстановка скобок. 7

1.4 Треугольник Каталана. 7

2 ЧИСЛА СТИРЛИНГА 10

2.1 Числа Стирлинга второго рода. 10

2.2 Числа Стирлинга первого рода. 11

3 ЧИСЛА БЕЛЛА 13

3.1 Определение 13

3.2 Свойства 14

4 ЧИСЛА ФИБОНАЧЧИ 15

4.1 Задача о кроликах. 15

4.2 Связь с золотым сечением. 16

4.3 Свойства чисел Фибоначчи. 18

5 БИБЛИОГРАФИЯ 20

 

ВВЕДЕНИЕ

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

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

 

 

1. ЧИСЛА КАТАЛАНА

Эжен Шарль Каталан(1814 – 1894) – бельгийский математик.

Первые несколько чисел  Каталана:

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, ...

Формула для вычисления n-го числа Каталана:

 ==

Существует несколько  десятков способов определения чисел  Каталана. Рассмотрим несколько классических способов.

1. Разрезание  треугольников.

Задача. Сколькими способами можно выпуклый n-угольник разрезать на треугольники диагоналями, не пересекающимися внутри этого n-угольника. Ответ для n=3 тривиален: никаких диагоналей проводить не надо (рис. 1). Для n=4 можно провести любую из двух диагоналей, так что способов 2 (рис. 2).

 

 

        рис.1                                                                           рис. 2                                                                                   

Для n=5 все 5 способов тоже, по сути, одинаковы: из некоторой вершины выходят две диагонали (рис. 3).

 

 

 

 

 

 

 

 

рис. 3

 

 

 

При n=6 получаем первый нетривиальный ответ: 14 способов (рис. 4).

                                             рис. 4

Для n=7 все способы рисовать не будем, можно выделить одну из сторон и расклассифицировать разрезания  в зависимости от  того, какой треугольник этой стороне примыкает (рис. 5).

                                               рис. 5

Имеем 5 различных  случаев. В первом и последнем из них количество разбиений равно 14, ибо после отрезания треугольника остается шестиугольник. Во втором и четвертом случаях при вырезании треугольника семиугольник распадается на треугольник и пятиугольник. Треугольник резать не надо, а пятиугольник, как мы уже знаем, дает 5 способов. В третьем случае от семиугольника остаются два четырехугольника. Поскольку каждый из них можно разбить двумя способами, получаем 2*2 = 4 варианта. Итак, семиугольник можно разбить всего

14 +5 + 2*2 + 5 + 14 = 42

способами.

 

Рассматривая восьмиугольник, аналогично получаем

42 + 14 + 2*5 + 5*2 + 14 + 42 = 132

способа. Для  девятиугольника имеем

132 + 42 + 2*14 + 5*5 + 14*2 + 42 + 132 = 429

способов, а  для десятиугольника – 

429 + 132 + 2*42 + 5*14 + 14*5 + 42*2 + 132 + 429 = 1430

способов.

Такие вычисления можно проводить  и дальше , и в итоге мы получим остальные числа Каталана.

2. Вычисление  произведений.

Рассмотрим другую - алгебраическую - задачу. Произведение аbс можно понимать двояко: (ab)c и а(bс). Произведение abcd можно понимать пятью способами: ((ab)c)d, (a(bc))d, a((bc)d), a(b(cd)) и (ab)(cd). Произведение abcde - четырнадцатью способами. Чтобы убедиться в этом, не обязательно их все выписывать. Достаточно заметить, что есть 5 способов вида a(bcde), 2 способа вида (ab)(cde), 2 способа вида (abc)(de) и 5 способов вида (abcd)e.

По одному из определений, число Каталана - это количество способов расставить скобки в произведение n множителей. Получается, что =  = 1, = 2,    = 5, = 14. Выведем для последовательности Каталана рекуррентную формулу. Для этого рассмотрим умножение, которое будет выполнено в последнюю очередь. Произведение ... получается,  в конечном счёте, как произведение некоторого произведения первых нескольких символов на некоторое произведение остальных:

... = (...)(...).

Первые r символов могут быть скомбинированы способами, последние n – r символом способами. Таким образом,

= ++…+. 

Это и есть рекуррентная формула для последовательности чисел Каталана. Например, чтобы  получить , достаточно выписать одно за одним первые 9 чисел Каталана, а под ними – те же числа, но в обратном порядке:

1 1 2 5 14 42 132 429 1430

1430 429 132 42 14 5 2 1 1

Умножив каждое верхнее число  на соответствующее нижнее и сложив, получим

= 4862.

Как видно, способ вычисления очередного члена последовательности такой же, как и в задаче о  разрезаниях на треугольники.

3. Расстановка скобок.

Рассмотрим какое-нибудь арифметическое выражение и сотрем все, кроме скобок. Получим некоторую  систему открывающих и закрывающих  скобок. Во-первых, открывающих скобок ровно столько же, сколько и  закрывающих. Во-вторых, ни в каком  начальном отрезке количество закрывающих  скобок не может оказаться больше количества открывающих скобок. Например, расстановки ) ( и ((( ))))( неправильные. Эти два условия не только необходимы, но и достаточны.

Рассмотрим несколько  примеров. Одна пара скобок может выглядеть  единственным способом: ( ). Две пары - двумя способами: ( )( ) или (( )). Три пары - пятью способами: ( )(  )(), ( )(( )), (( ))( ), (( )( )) или ((( ))). Четыре пары, как нетрудно проверить,- четырнадцатью способами. Что понять, сколькими способами могут выглядеть правильно расставленные 5 пар скобок, рассмотрим закрывающую скобку, парную к первой открывающей скобке. Остальные четыре пары тогда разделятся на две группы: расположенные внутри рассмотренной пары и расположенные справа от нее. (Разумеется, любая из этих групп может состоять из 0 скобок.) Способов, когда все четыре пары внутри или все четыре справа, - по 14 в каждом случае. Когда три пары внутри, а одна справа – 5 способов. Столько же – когда одна внутри, а три справа. Наконец, когда две пары внутри, а две справа, имеем 2*2 = 4 способа. Итого,

14 + 5 + 2*2 + 5 + 14 = 42

Очевидно, что для случаев 6 пар скобок и больше, получим  такую же последовательность чисел  как и в задаче о разрезаниях  на треугольники, то есть числа Каталана.

4. Треугольник Каталана.

Известный треугольник Паскаля (рис.6) получается, если начать с верхней  единицы и затем действовать  по правилу «каждое очередное  число равно сумме чисел, расположенных  над ним «справа и слева» (а  на краях — единицы). Он обладает многими интересными свойствами. Но сейчас речь не о нем. Давайте  проведем вертикальную черту, левее  которой заходить нельзя, и будем  выписывать числа так, словно мы составляем треугольник Паскаля (рис. 7). На самой  левой вертикали - числа Каталана!

                                   1

1. 1

                    1              2              1

             1              3              3           1

      1            4               6             4          1

1          5              10           10           5         1

рис. 6

 

 

1

      1

1           1

       2          1

2            3         1

        5           4        1

5             9          5         1

        14        14         6         1

14          28         20        7         1

        42         48        27       8         1

42           90        75        35       9         1

        132      165      110      44      10        1

132        297      275      154     54       11       1

                   429       572      429      208    65        12      1

                                 рис. 7

Почему же на левой вертикали возникают числа Каталана? Другими словами, как связать треугольник Каталана с какой-нибудь из ранее рассмотренных задач, например, с задачей о правильных расстановках скобок?

Открывающей скобке сопоставим движение вниз-вправо, а закрывающей – движение вниз-влево. Путь возвращается к исходной вертикали, если количества открывающих и закрывающих скобок уравнялись. Путь пересекает эту вертикаль, как только количество закрывающих скобок превышает количество открывающих. Правильные расстановки скобок взаимно однозначно соответствуют правильным - т.е. возвращающимся к вертикальной черте и не пересекающим ее - путям. На рисунках 8, 9 и 10 проиллюстрированы случаи 1, 2 и 3 пар скобок соответственно.

 

 

 

       ( )      

рис. 8

 

 

                             (( ))                                                      ( )( )

                                                  рис. 9

 

     

 

 

   ((( )))                      (( )( )) ( )(( )) ( )( )( ) (( ))( )

рис.10

Итак, любой правильной расстановке  скобок соответствует путь в треугольнике Каталана;   любое  число треугольника Каталана равно количеству путей, которыми можно прийти в соответствующую  точку вершины.

В завершении, перечислю задачи, которые приводят к определению  чисел Каталана. Итак, n-ое число Каталана равно количеству:

• способов расположить несколько одинаковых бревен, когда в нижнем ряду их n – 1;
• путей Дика, т.е. путей, начинающихся в начале координат, не спускающихся ниже оси абсцисс, где каждый шаг - перемещение на единицу вправо и на единицу вверх или вниз, оканчивающихся на оси абсцисс, обладающих n – 1 точками локального минимума (другими словами, n – 1 пиками) и не имеющих трех подряд идущих шагов в одном и том же направлении;
• путей Дика, оканчивающихся в точке (2n; 0), ни один из пиков (т.е. локальных максимумов) которых не расположен на высоте 2;
• горизонтальных полимино ширины n;
• симметричных полимино периметра 4(2n - 1);
• последовательностей ≤≤...≤  натуральных чисел,   удовлетворяющих неравенствам ≤ k , где 1≤ k < n , а именно, при n = 4 это последовательности 1 ≤ 1 ≤ 1, 1 ≤ 1 ≤ 2, 1 ≤ 1 ≤ 3, 1 ≤ 2 ≤ 2, 1 ≤ 2 ≤ 3;

 

 

 

 

 

 

 

 

 

 

2. ЧИСЛА СТИРЛИНГА

Джеймс Стирлинг(1692 – 1770) – шотландский математик.

Эти числа выступают в  двух разновидностях, традиционно носящих  незатейливые названия « чисел Стирлинга  первого и второго рода». До сих  пор нет общепринятого обозначения  для этих чисел, некоторые обозначают так: {}- числа Стирлинга второго рода, а через [] – первого рода; S(n, k) – числа Стирлинга второго рода, s(n, k) – первого рода.

Числа Стирлинга второго  рода возникают намного чаще, чем  числа Стирлинга первого рода, так что вторые рассмотрим первыми (И сам Стирлинг в своей книге  в первую очередь рассмотрел этот род чисел). 

1. Числа Стирлинга  второго рода.

Символом S(n, k) обозначается число способов разбиения множества из n элементов на k непустых подмножеств. S(n, k) читается так: k подмножеств из n. Так, существует 7 способов разбиения четырёхэлементного множества на две части:

{1, 2, 3}U{4}, {1, 2, 4}U{3}, {1, 3, 4}U{2}, {2, 3, 4}U{1},

{1, 2}U{3, 4}, {1, 3}U{2, 4}, {1, 4}U{2, 3},

следовательно, S(4, 2) = 7.

Рассмотрим  значения чисел Стирлинга для  малых значений k:

1. k = 0. Существует только один способ разбиения пустого множества на нулевое число непустых частей, поэтому S(0, 0) = 1. Для непустого множества нужна по крайней мере хотя бы одна часть, так что S(n, 0) = 0  при n > 0.

2. k = 1. Существует только один способ помещения n элементов в одно-единственное непустое множество, поэтому S(n, 1) = 1 при n > 0. Однако S(0, 1) = 0, так как 0-элементное множество пусто.

3. k = 2. Очевидно, что S(0, 2) = 0. Если же множество из n > 0 объектов разделено на две непустые части, то одна из этих частей содержит последний объект и некоторое подмножество из первых n — 1 объектов. Имеется способов выбора последнего подмножества, ибо каждый из первых n — 1 объектов либо входит, либо не входит в него. Но нам вовсе не нужно помещать в него все эти объекты, поскольку у нас должны остаться две непустые части. Поэтому вычтем 1:

S(n, 2) = – 1, целое n>0.

Выведем рекуррентное соотношение, при помощи которого можно  будет вычислить значения S(n, k). Если задано множество из n > 0 объектов, которое должно быть разбито на k непустых частей, то мы либо помещаем последний объект в отдельный класс, а оставшиеся n – 1 объект разбиваем на k – 1 часть S(n – 1, k – 1) способами, либо помещаем его в любую из k частей, на которые разбиты n – 1 объект. В последнем случае имеется     k*S(n - 1, k)  возможных вариантов, поскольку каждый из S(n – 1, k) способов распределения первых n – 1 объектов по k непустым частям дает k подмножеств, с которыми можно объединить n -ый объект. Имеем рекуррентную формулу: